Take the 2-minute tour ×

Given a set integers, the problem consists of finding the number of possible arithmetic series of length 3. The set of integers may or may not be sorted.

I could implement a simple bruteforce algorithm taking time O(n^3) but time efficiency is important and the set of integers can be as large as 10^5. This means bruteforce obviously won't work. Can anyone suggest some algorithm/pseudocode/code in c++?

An example: there are 4 numbers 5,2,7,8 . Clearly there is only one such possibility - (2,5,8) in which the common difference is 3, so our answer is 1.

EDIT:I forgot to mention one important property - each number of set given is between 1 to 30000 (inclusive).

share|improve this question
guess is that we sort numbers in O(n log n) and remove duplicacy , but removing duplicacy can be used just as optimization , not as actual algorithm . But i think solution revolves somewhere around here , the problem becomes interesting due to its constraints . –  Maggi Iggam Nov 10 '12 at 18:29
Sounds familiar : codechef.com/NOV12/problems/COUNTARI –  axiom Nov 10 '12 at 18:36
Problem is almost same because that is the problem ;) –  axiom Nov 10 '12 at 18:43
@user1795954 if you are also Maggi Iggam please ask a moderator to reconnect your accounts (you can flag this question to do so.) Otherwise editing the question to add more information will continue to be rejected. –  Kate Gregory Nov 10 '12 at 18:44
@KateGregory : gud observation , but it is not so - i knew the question source was from codechef so i private messaged Maggi Iggam (he is in my contacts) to add that important propert :) –  Maggi Iggam Nov 10 '12 at 18:58
show 1 more comment

2 Answers

up vote 3 down vote accepted

You can do it in O(N^2) as follows: create a hash set of your integers so that you could check a presence or absence of an element in O(1). After that, make two nested loops over all pairs of set elements {X, Y}. This is done in O(N^2).

For each pair {X, Y}, assume that X < Y, and calculate two numbers:

Z1 = X - (Y-X)
Z2 = Y + (Y-X)

A triple {X, Y, Zi} form an arithmetic sequence if Zi != X && Zi != Y && set.contains(Zi)

Check both triples {X, Y, Z1} and {X, Y, Z2}. You can do it in O(1) using a hash set, for a total running time of the algorithm of O(N^2).

share|improve this answer
thanks very much , but i think O(n) solution also exist , can you please use property i have just added now ? Maybe that can lead your superb brain to O(n) :) –  Maggi Iggam Nov 10 '12 at 18:41
@user1795954 I don't think you can do it in O(N), but with the limits of 30K you can use an array of booleans (counters if your set is really a bag that allows duplicates) instead of a hash set to perform your checks much faster. –  dasblinkenlight Nov 10 '12 at 19:02
Yepp i agree with you @dasblinkenlight –  Maggi Iggam Nov 10 '12 at 19:17
@dasblinkenlight , what do you think now after reading answer below :P –  Maggi Iggam Nov 11 '12 at 9:12
@MaggiIggam It may be workable, but it's almost certainly an overkill for a codechef-level problem. –  dasblinkenlight Nov 11 '12 at 10:35
add comment

An alternative solution that is O(N+BlogB) (where B is the maximum size of the integers - in your case 30,000) is to consider the histogram H, where H[x] is the number of times x is present in the sequence.

This histogram can be computed in time N.

You are seeking elements a,b,c such that b-a=c-b. This is equivalent to 2b=a+c.

So the idea is to compute a second histogram G[x] for a+c and then loop through all elements b and add H[b]*G[2b] to the total. This takes time O(B).

(G[x] is the number of times in the sequence there are a pair of values a,b such that x=a+b.)

The only difficulty is computing G[x], but this can be done using the Fast Fourier Transform to convolve H[x] with itself in time O(BlogB).

share|improve this answer
It appears to be a very potential solution (vote up) , but i really cudnt understand completly , so can you supply code snippet ? –  Maggi Iggam Nov 11 '12 at 9:10
There is a detailed explanation (including code samples) of how to do the convolution at hebb.mit.edu/courses/9.29/2002/readings/c13-1.pdf –  Peter de Rivaz Nov 11 '12 at 9:20
Hey , man that was excellent , bit it went much off my head :D –  Maggi Iggam Nov 11 '12 at 11:29
add comment

Your Answer


