Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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
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|cite|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


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.