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.

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

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$.

  • $\begingroup$ I just solved it using this approach,when I refreshed I saw your answer :-) $\endgroup$ – Quixotic Jan 8 '11 at 15:13

Your Answer

