Arithmetic Sequence
February 23, 2016
This is easy if you first sort the input, but that takes time O(n log n). For a better solution, first find the minimum, maximum, and length of the list of integers, then calculate the difference as (max − min) / (len − 1). That takes O(n). Then divide each of the inputs by the difference after subtracting the minimum. If any do not divide, the input cannot form a sequence. But if they do divide, sum the quotients as you go; the sum must be len × (len + 1) / 2, otherwise there is a duplicate. The check also takes O(n) time, so the entire algorithm is O(n), and O(1) space for the minimum, maximum, length, and sum of quotients:
(define (seq? xs)
(let* ((mn (apply min xs))
(mx (apply max xs))
(len (length xs))
(diff (/ (- mx mn) (- len 1))))
(if (not (integer? diff)) #f
(= (* len (+ len 1) 1/2)
(apply +
(map (lambda (x)
(if (zero? (remainder x diff))
(quotient x diff)
0))
(map (lambda (x) (- x mn (- diff)))
xs)))))))
And here are two examples:
> (seq? '(1 3 5 7 9)) #t > (seq? '(1 4 5 6 9)) #f
You can run the program at http://ideone.com/7U9jZA.
Programming Praxis 
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.
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))))@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.
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
And yet (1 1 1 1) is an arithmetic sequence by the definition given, so the test should succeed, not fail.
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.
The size of a bit array would depend on the values in the array rather than n.
@John: I’m assuming we have found the (potential) increment value and done the divisions, so we just need n entries in the array.
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);
}
(@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])))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]
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
There might a simpler solution in O(n) time
Sorry, just realized that the solution posted above take O(n log n) time because of the sort.