Arithmetic Sequence

February 23, 2016

Today’s exercise is an interview question from Amazon:

Determine if a list of integers forms an arithmetic sequence. For instance, the integers 1, 2, 3, 4, 5 form an arithmetic sequence because the differences between them are all the same, but the integers 1, 2, 4,8, 16 do not form an arithmetic sequence because the differences betweent them are not all the same. The input need not be sorted, so the integers 3, 2, 5, 1, 4 also form an arithmetic sequence.

Your task is to write a function that determines if a list of integers forms an arithmetic sequence. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

14 Responses to “Arithmetic Sequence”

  1. Jussi Piitulainen said

    I don’t think summing the steps is sufficient. First I didn’t think of it myself, then I thought it was clever, and then I began to have doubts. Here’s a counterexample.

    scheme@(guile-user)> (seq? '(1 3 5 7))
    $1 = #t
    scheme@(guile-user)> (seq? '(1 1 7 7))
    $2 = #t
    scheme@(guile-user)> 
    
  2. Jussi Piitulainen said

    So I have an O(n) time, O(n) space solution.

    from itertools import repeat
    
    def isari(seq):
        '''If a sequence of at least two integers can be ordered to be an
        arithmetic sequence (constant difference).'''
        i, a, n = min(seq), max(seq), len(seq) # O(n) time
        delta, error = divmod(a - i, n - 1)
        if error: # integer spacing fails
            return False
        else:
            there = list(repeat(0, n)) # O(n) space
            for m in seq: # O(n) time
                k, error = divmod(m - i, delta)
                if error: # delta spacing fails
                    return False
                else:
                    there[k] += 1 # this pigeon is there
            else:
                return all(there) # O(n) time
    
    print(*map(isari, ((3, 6, 9), (21, 7), (1, 2, 3, 4, 5), (1, 3, 5, 7))))
    print(*map(isari, ((3, 6, 3), (1, 2, 3, 4, 6), (1, 1, 7, 7))))
    print(*map(isari, ((3, 6, 0), (1, 2, 3, 0, -1))))
    
  3. programmingpraxis said

    @Jussi: Oh. I missed that. Thanks for pointing it out.

    In that case, I think the proper answer is to insert the integers in a hash table. Any duplicates cause a failure, in addition to the failure reported when the division fails. That still has time complexity O(n), but raises the space complexity from O(1) to O(n).

    I guess that makes sense. If you can’t permit duplicates, then somehow or other you have to keep track of everything you’ve seen before, so O(1) space complexity isn’t possible.

  4. John Cowan said

    That’s the problem with clever solutions generally: one is often much less sure that they work (and sometimes they don’t work), and often linearithmic performance is just fine. “When in doubt, use brute force.” —Dennis Ritchie

  5. John Cowan said

    And yet (1 1 1 1) is an arithmetic sequence by the definition given, so the test should succeed, not fail.

  6. matthew said

    Indeed. Not sure a hash table is necessary – just checking off the numbers in an array (as in Jussi’s solution) is all that is needed – and that could just be a bit array, still O(n) space but a nice small constant factor.

    Maybe we should worry about the complexity of the divisions too, if we are going to do these things properly.

  7. John Cowan said

    The size of a bit array would depend on the values in the array rather than n.

  8. matthew said

    @John: I’m assuming we have found the (potential) increment value and done the divisions, so we just need n entries in the array.

  9. IvAn said

    O(n) solution in C

    int is_arithmetic_sequence(int *list, unsigned int size)
    {
    int min,max,sum,i,res;
    if( size<3 || !list )
    {
    return 0;
    }
    min=list[0];
    max=list[0];
    sum=0;
    for(i=0;i<size;i++)
    {
    sum+=list[i];
    if(list[i]max)
    {
    max = list[i];
    }
    }
    res=(min+max)*size/2;
    return (res==sum);
    }

  10. Jussi Piitulainen said

    (@IvAn: Use the sourcecode tags, in square brackets, to keep the indentation. See link in the red bar at the top.)

    Here’s a version with o(n!) worst-case time, O(n) space. It finds the least two elements, if any, in O(n) time, and then compares the permutations of the original sequence to an appropriate canonical sequence. Division by zero is succesfully avoided. Whether sorting is avoided or only implicit, I prefer not to say. Replacing the generate-and-test step with explicit sorting would give an O(n log n) time version. (This is Python. The keyword parameters to Python’s min and max are pretty cool.)

    from itertools import permutations
    from functools import partial
    from operator import eq as equal
    
    def skiponce(seq, o):
        '''Generator of seq that skips one o.'''
        skup = False
        for e in seq:
            if skup:
                yield e
            elif e == o:
                skup = True
            else:
                yield e
    
    def isarit(seq):
        '''If sorted(seq) has constant differences, now without division
        by zero. Allows constant sequence, empty sequence, and single
        element sequence.'''
        seq = list(seq)
        i = min(seq, default = 0)
        s = min(skiponce(seq, i), default = i)
        can = tuple(i + k * (s - i) for k in range(len(seq)))
        return any(map(partial(equal, can), permutations(seq)))
    
    print(*map(isarit, ([], [3], [3, -1], [3, 1, 4, 2], [3, 3], [3, 3, 3])))
    print(*map(isarit, ([3, 1, 4, 1], [3, 1, 4], [1, 1, 7, 7])))
    
  11. catalinc said

    The following solution seems to work:

    [codesource lang=”python”]
    def is_arithmetic_seq(l):
    m = min(l)
    s = sum(l)
    n = len(l)
    # S = X_min + (X_min + diff) + (X_min + 2*diff) + …
    # = N * X_min + diff * (N * (N – 1) / 2)
    # so (S – X_min) mod (N * (N – 1) / 2) should be 0
    return (s – n * m) % ((n * (n – 1)) / 2) == 0

    if __name__ == ‘__main__’:
    test_data = [[3, 2, 5, 1, 4], [1, 2, 4, 8, 16], [2, 8, 3], [1, 1, 1, 1]]
    for l in test_data:
    print(is_arithmetic_seq(l))

    # prints:
    # True
    # True
    # False
    # False
    # True
    [/sourcecode]

  12. catalinc said

    Edit: fix source code formatting.

    The following solution seems to work:

    def is_arithmetic_seq_fast(l):
    m = min(l)
    s = sum(l)
    n = len(l)
    # S = X_min + (X_min + diff) + (X_min + 2*diff) + …
    # = N * X_min + diff * (N * (N – 1) / 2)
    # so (S – X_min) mod (N * (N – 1) / 2) should be 0
    return (s – n * m) % ((n * (n – 1)) / 2) == 0

    if __name__ == ‘__main__’:
    test_data = [[3, 2, 5, 1, 4], [1, 2, 4, 8, 16], [2, 8, 3], [1, 1, 1, 1]]
    for l in test_data:
    print(is_arithmetic_seq_fast(l))

    # prints:
    # True
    # False
    # False
    # True

  13. describe said

    There might a simpler solution in O(n) time

    
    def arithmeticSequence(A):
    	retVal = True
    	A.sort()
    	diff = -1
    	
    	if len(A) < 2:
    		return False
    	else:
    		diff = A[1] - A[0]
    	
    	for j in range (1,len(A)):
    		if diff != A[j] - A[j-1]:
    			retVal = False
    			break
    
    	return retVal
    
    
  14. describe said

    Sorry, just realized that the solution posted above take O(n log n) time because of the sort.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: