CODEWITHSUNDEEP
algorithm
Hao Cui
Hao Cui

Reputation: 11

Ouput all possibilities, could be three int number as example belowed

Given a sorted array, output all triplets such that a-b=c, the example of array is: {-24, -15, -8, -6, 0, 3, 6, 9, 17, 36}

Upvotes: 1

Views: 86

Answers (3)

Grigor Gevorgyan
Grigor Gevorgyan

Reputation: 6853

I'll suggest an O(n^2) solution based on the following property: if you fix a and sequentially increase b then c is decreasing. So you can do as following:

    for( i = 0; i < arr.size(); i++ ) // index of a
    {
        t = arr.size() - 1; // index of possible c
        for( j = 0; j < arr.size(); j++ ) // index of b
        {
            a = arr[ i ];
            b = arr[ j ];
            c = a - b;
            while( t >= 0 && arr[ t ] > c ) // using monotonicity
               t--;
            if( t >= 0 && arr[ t ] == c )
            { /* output a, b, c */ }
        }
    }

Upvotes: 3

גלעד ברקן
גלעד ברקן

Reputation: 23955

Haskell version:

triples set = 
  [[a,b,c] | a <- set, b <- set, b /= a, c <- set, c /= b && c /= a, a - b == c]

*Main> triples [-24, -15, -8, -6, 0, 3, 6, 9, 17, 36]
[[-15,-24,9],[-15,9,-24],[-6,-15,9],[-6,9,-15],[0,-6,6],[0,6,-6],[3,-6,9],[3,9,-6],[9,-8,17],[9,3,6],[9,6,3],[9,17,-8]]

Upvotes: 0

IVlad
IVlad

Reputation: 43507

Can be done in O(n^2) by storing all a - b in a hash table then querying the hash for each element c in the array.

Upvotes: 1

Related Questions