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