Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given a sequence of N numbers, how can we find the minimum number of numbers to be inserted to make this sequence to an Arithmetic progression.(we can insert at any position of this sequence)

For example consider a sequence of $4$ numbers :$1,3,7,13$ Here we have to insert at-least $3$ more numbers ($5,9,11$) so that $1,3,5,7,9,11,13$ becomes an A.P with common difference $2$.

I am inquisitive to know an an efficient algorithm for this problem.

share|improve this question
    
This isn't always possible, e.g. consider the sequence 1, 2, 1. –  Qiaochu Yuan Jan 8 '11 at 14:53
    
You can (safely) assume that the $N$ numbers are such, that it will always produce a solution. –  Quixotic Jan 8 '11 at 14:55

1 Answer 1

up vote 3 down vote accepted

Take the gcd $d$ of the differences between consecutive numbers in the sequence $a_1, ... a_n$; at worst this should take $O(n \log m)$ time where the numbers have size $O(m)$. The shortest arithmetic progression containing these numbers in the correct order has common difference $d$ and first and last terms $a_1, a_n$, so the total number of terms is $\frac{a_n - a_1}{d} + 1$ and the number of terms that need to be inserted is $\frac{a_n - a_1}{d} + 1 - n$.

share|improve this answer
    
I just solved it using this approach,when I refreshed I saw your answer :-) –  Quixotic Jan 8 '11 at 15:13

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.