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

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.

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

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

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