How to find out if an arithmetic sequence exists in an array-CodePudding

If there is an array that contains random integers in ascending order, how can I tell if this array contains a arithmetic sequence (length>3) with the common differece x?

Example: Input: Array=[1,2,4,5,8,10,17,19,20,23,30,36,40,50] x=10 Output: True

Explanation of the Example: the array contains [10,20,30,40,50], which is a arithmetic sequence (length=5) with the common differece 10.

Thanks!

I apologize that I have not try any code to solve this since I have no clue yet.

CodePudding user response：

Try from 1: check the presence of 11, 21, 31... (you can stop immediately)

Try from 2: check the presence of 12, 22, 32... (you can stop immediately)

Try from 4: check the presence of 14, 24, 34... (you can stop immediately)

...

Try from 10: check the presence of 20, 30, 40... (bingo !)

You can use linear searches, but for a large array, a hash map will be better. If you can stop as soon as you have found a sequence of length > 3, this procedure takes linear time.

CodePudding user response：

Scan the list increasingly and for every element v, check if the element v 10 is present and draw a link between them. This search can be done in linear time as a modified merge operation.

E.g. from 1, search 11; you can stop at 17; from 2, search 12; you can stop at 17; ... ; from 8, search 18; you can stop at 19...

Now you have a graph, the connected components of which form arithmetic sequences. You can traverse the array in search of a long sequence (or a longest), also in linear time.

In the given example, the only links are 10->-20->-30->-40->-50.

CodePudding user response：

You can solve your problem by using 2 loops, one to run through every element and the other one to check if the element is currentElement x, if you find one that does, you can continue form there.
With the added rule of the sequence being more than 2 elements long, I have recreated your problem in FREE BASIC:

DIM array(13) As Integer = {1, 2, 4, 5, 8, 10, 17, 19, 20, 23, 30, 36, 40, 50}
DIM x as Integer = 10
DIM arithmeticArrayMinLength as Integer = 3
DIM index as Integer = 0

FOR position As Integer = LBound(array) To UBound(array)
    FOR position2 As Integer = LBound(array) To UBound(array)
        IF (array(position)   x = array(position2)) THEN
            position = position2
            index = index   1
        END IF
    NEXT
NEXT
IF (index <= arithmeticArrayMinLength) THEN
    PRINT false
ELSE 
    PRINT true
END IF

Hope it helps