CODEWITHSUNDEEP
algorithm
Maggi Iggam
Maggi Iggam

Reputation: 692

Finding the number of possible arithmetic series of 3 among a given set of numbers

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

Upvotes: 2

Views: 2103

Answers (2)

Peter de Rivaz
Peter de Rivaz

Reputation: 33509

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

Upvotes: 3

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726599

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

Upvotes: 3

Related Questions