CODEWITHSUNDEEP
arraysalgorithmsequencemath
Haim Evgi
Haim Evgi

Reputation: 125594

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

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 

4,6,8

or

 4,5,6

remark : the minimum numbers in sequence is 3

Upvotes: 3

Views: 10197

Answers (5)

Eric
Eric

Reputation: 16931

Here's the code in Swift 4:

extension Array where Element == Int {

    var isArithmeticSequence: Bool {
        let difference = self[1] - self[0]
        for (index, _) in self.enumerated() {
            if index < self.count-1 {
                if self[index + 1] - self[index] != difference {
                    return false
                }
            }
        }
        return true
    }

    var arithmeticSlices: [[Int]] {

        var arithmeticSlices = [[Int]]()
        var sliceSize = 3
        while sliceSize < self.count+1 {

            for (index, _) in self.enumerated() {

                if (index + sliceSize-1) <= self.count - 1 {

                    let currentSlice = Array(self[index...index + sliceSize-1])
                    if currentSlice.isArithmeticSequence {
                        arithmeticSlices.append(currentSlice)
                    }
                }
            }
            sliceSize+=1
        }
        return arithmeticSlices
    }
}


let A = [23, 24, 98, 1, 2, 5]
print(A.arithmeticSlices) // []

let B = [4, 7, 10, 4,5]
print(B.arithmeticSlices) //[[1, 2, 3], [2, 3, 4], [3, 4, 5], [1, 2, 3, 4], [2, 3, 4, 5], [1, 2, 3, 4, 5]]

let C = [4, 7, 10, 23, 11, 12, 13]
print(C.arithmeticSlices) // [[4, 7, 10], [11, 12, 13]]

Upvotes: 0

smirkingman
smirkingman

Reputation: 6368

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
Next
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
    Next
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
    Next
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)
    Next
    ans = text & " " & Mid(ans, 2)
    Debug.Print ans
End Sub

Results

findthem
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!

HTH

Upvotes: 2

Vladimir
Vladimir

Reputation: 170859

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

Upvotes: 1

Kirk Fernandes
Kirk Fernandes

Reputation: 111

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

Upvotes: 1

Justin L.
Justin L.

Reputation: 13600

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.

Upvotes: 1

Related Questions