Take the 2-minute tour ×

i have sorted array of numbers like

1, 4, 5 , 6, 8

what is the way to find out if this array contain Arithmetic progression (sequence) ?

like in this example




remark : the minimum numbers in sequence is 3

share|improve this question
Every numerical array (of length ≥2) contains an arithmetic progression of 2 elements. –  KennyTM Nov 2 '10 at 7:30
of course i update from 3 numbers and above, like in the example –  Haim Evgi Nov 2 '10 at 7:32
would you pick 4,6,8 over 4,5,6, in this example? Why? –  Matt Ellen Nov 2 '10 at 9:05
you right 4,5,6 is also sequence. it need to find this –  Haim Evgi Nov 2 '10 at 9:15
For O(a_n log a_n) algorithm, check stackoverflow.com/questions/1560523 –  sdcvvc Nov 3 '10 at 10:41
add comment

5 Answers

up vote 2 down vote accepted

You can solve this recursively, by breaking it into smaller problems, which are:

  • Identify the pairs {1,4},{1,5}...{6,8}
  • For each pair, look for sequences with the same interval

First create the scaffolding to run the problems:

Dim number(7) As Integer
Dim result() As Integer
Dim numbers As Integer
Sub FindThem()
number(1) = 1
number(2) = 4
number(3) = 5
number(4) = 6
number(5) = 8
number(6) = 10
number(7) = 15
numbers = UBound(number)
ReDim result(numbers)
Dim i As Integer
For i = 1 To numbers - 2
    FindPairs i
End Sub

Now iterate over the pairs

Sub FindPairs(start As Integer)
    Dim delta As Integer
    Dim j As Integer
    result(1) = number(start)
    For j = start + 1 To numbers
        result(2) = number(j)
        delta = result(2) - result(1)
        FindMore j, 2, delta
End Sub

Finding sequences as you go

Sub FindMore(start As Integer, count As Integer, delta As Integer)
    Dim k As Integer
    For k = start + 1 To numbers
        step = number(k) - result(count)
        result(count + 1) = number(k) ' should be after the if statement
                                      ' but here makes debugging easier
        If step = delta Then
            PrintSeq "Found ", count + 1
            FindMore k, count + 1, delta
        ElseIf step > delta Then ' Pointless to search further
            Exit Sub
        End If
End Sub

This is just to show the results

Sub PrintSeq(text As String, count As Integer)
    ans = ""
    For t = 1 To count
        ans = ans & "," & result(t)
    ans = text & " " & Mid(ans, 2)
    Debug.Print ans
End Sub


Found  1,8,15
Found  4,5,6
Found  4,6,8
Found  4,6,8,10
Found  5,10,15
Found  6,8,10

Edit: Oh, and of course, the array MUST be sorted!


share|improve this answer
add comment

Certainly not the optimal way to solve your problem, but you can do the following:

Iterate through all pairs of numbers in your array - each 2 numbers fully define arithmetic sequence if we assume that they're 1st and 2nd progression members. So knowing those 2 numbers you can construct further progression elements and check if they're in your array.

If you want just find 3 numbers forming arithmetic progression then you can iterate through all pairs of non-adjacent numbers a[i] and a[j], j > i+1 and check if their arithmetic mean belongs to array - you can do that using binary search on interval ]i,j[.

share|improve this answer
add comment

First, I will assume that you only want arithmetic sequences of three terms or more.

I would suggest checking each number a[i] as the start of an arithmetic sequence, and a[i+n] as the next one.

Now that you have the first two terms in your series, you can find the next. In general, if x is your first term and y is your second, your terms will be x + i*(y-x), with the first term at i = 0. The next term will be x + 2*(y-x). Search your array for that value. If that value is in your array, you have an arithmetic sequence of three items or more!

You can continue with i=3, i=4, etc. until you reach one that is not found in your array.

If l is the size of your array, do this for all i from 0 to l-2, and all n from 0 to l-i-1

The only major caveat is that, in the example, this will find both sequences 4,6,8 as well as 6,8. Technically, both of them are arithmetic sequences in your series. You will have to more specifically define what you want there. In your case, it might be trivial to just check and eliminate all progressions that are totally contained inside others.

share|improve this answer
add comment

what i try to do is find all combination of 3 numbers that be in this array.

and find the distance between them if it is equal , we found

like :

for ($i = 1; $i <= $countArray - 2; $i++) {
     for ($j = $i+1; $j <= $countArray - 1; $j++) {         
    for ($k = $j+1; $k <= $countArray; $k++) {
            if($array[$j]-$array[$i] == $array[$k]-$array[$j]){
             # found 
share|improve this answer
add comment

The general idea is to pick an element as your a_1, then any element after that one as your a_2, compute the difference and then see if any other elements afterwards that match that difference. As long as there are at least 3 elements with the same difference, we consider it a progression.

progression (A, n)
   for i = 1 ... n - 2
      a_1 = A[i]
      for j = i + 1 ... n - 1
         a_2 = A[j]
         d = a_2 - a_1
         S = [ i, j ]
         for k = j + 1 ... n
            if ( d == ( a[k] - a[S.last] ) )
               /* Append the element index to the sequence so far. */
               S += k
         if ( |s| > 2 )
            /* We define a progression to have at least 3 numbers. */
            return true
   return false

You can modify the algorithm to store each set S before it is lost, to compute all the progressions for the given array A. The algorithm runs in O(n^3) assuming appending to and getting the last element of the set S are in constant time.

Although I feel like there might be a more efficient solution...

share|improve this answer
add comment

Your Answer


