CareerCup

1.The idea is to find (a,b,c) such that a-b=c ..in other words, a=b+c;

2. We know that if an array is sorted, we can find two numbers(b,c) which sum up to a
particular value(a) in O(n) time.

3. So start from the end of the array.For each value a[i], search for sum=a[i] between a[0] and a[i-1]. Starting from the end makes sure we can eliminate any option to the right of that element as such an element will not satisfy the equation a=b+c

4. Complexity =n*O(n) =O(n^2);

Here is the output for above example:

-12 = -7 - 5
-12 =  3 - 15
 -7 = -4 - 3
 -7 =  3 - 10
 -7 =  9 - 16
 -4 =  5 - 9
  3 = -4 - -7
  5 = -7 - -12
  5 = 15 - 10 
 10 = 3 - -7 
 10 = 15 - 5

You should assume that no number is repeated.

I find a similar problem (appeared on google interview) here:
careercup.com/question?id=9449188

However, that problem is simpler as it asks to output pair of integers from a given sorted array A (with no duplicates) such that a - b = k (given integer). I could come up to solve it in O(n) as below. However, the scenario for above case is different, as the target is a variable (not a fixed value k).

void diffOfTwo (int a[], int n, int k)		
{											for (int j = 1, i = 0; j < n; j++)
	{
		while ( i < j) 
		{
			if ( a[j] - a[i] == abs (k) ) 
			{
                                //solution found
				i++, j++;
			}
		
			else if ( a[j] - a[i] > abs(k) ) 
				i++;

			else j++;
		}
	}
}

Essentially - find the triplets that a = b+c.
If the elements are integers and have an upperbound, i.e., array contains integers less than 'K', then it is easy to do this O(n^2)
We need to check for every pair of numbers if their sum is already in the array.
Given the array length is n, we have O(n^2) checks to make.
But then, each check will take atmost K checks -- O(1). Here's how:
If we are analysizing say b and c. Because it is sorted integer array, the sum (b+c) must lie within 'c'-distance of 'b' or 'b'-distance of 'c'.
The direction of search will depend on the sign of either of b or c.
So, we have an O(n^2) solution.

add all the possible sums i.e. a+b from the array to a set. Now check the array if the element is in the set.
eg: a[]={2,3,5,4,9};
set: { 5,6,7,8,9,11,12,13,14 }
ans: 2,3,5 and 4,5,9
complexity: O(n**2 + n) ~ O(n**2)

#include <iostream>
using namespace std;
void binder(int*a, int n) {
  for (int i = 0; i < n; i++) {
    int current = a[i];
    int left = 0;
    int right = n-1;
    while (left < right) {
      if ( left == i ) {
        left++;
        continue;
      }

      if (right == i) {
        right--;
        continue;
      }

      if (a[left] + a[right] < current) {
        left++;
      } else if (a[left] + a[right] > current) {
        right--;
      } else {
        cout << current << " = " << a[left] << " + " << a[right] <<endl;
        left++;
        right--;
      }
    }
  }
}

int main() {
  int a[] = {-12, -7, -4, 0, 3, 5, 9, 10, 15, 16};
  binder(a, 10);
  return 0;
}

1. insert array to a hash table. O(n)
2. select a and b in two loops. O(n^2)
3. check if there is c in the hash table such that c = a-b. O(1)

=> O(n^2)

since no. are in increasing order and not repeated ,triplet(a,b,c) must be unique.
think a=b-c as b=a+c
let i=0,j=lastindex,k=lastindex of array
while(i<j)
{ j=k=last;
while(i<k)
{ if(a[i]+a[j]==a[k])
{ //a triplet found
j--;k--;
}
else if(a[i]+a[j]<a[k])
k--;
else
j--;
}
}

my idea is similar to anonymous on August 04, 2011(given above) modified for a-b=c;
complexity=O(n^2).

we should solve the a=b+c problem.
1-for each pair compute b+c and store it in another data structure(e.x. array). it takes O(n^2).
notion: Since the input array is sorted the summation array which keeps b+c can be easily computed in such a way to be sorted too!
2-match the input array with the summation array to find a=b+c. do this by binary search on the summation array per each number in input array. it takes O(n*log(2^n))=O(2n*log(n))

so the complexity is O(n^2)+O(nlogn)= O(n^2)

public void FindTriplets(int[] inp)
        {
            //all a-b=c combinations
            Hashtable ht = new Hashtable();
            for (int i = 0; i < inp.Length; i++)
            {
                ht[inp[i]] = 1;
            }
            for (int i = 0; i < inp.Length; i++)
            {
                for (int j = 0; j < inp.Length; j++)
                {
                    if (i != j)
                    {
                        int diff = inp[i] - inp[j];
                        if (!(diff == inp[i] || diff == inp[j]))
                        {
                            if (ht.Contains(diff))
                            {
                                Console.WriteLine(inp[i].ToString() + "-" + inp[j].ToString() + "=" + diff.ToString());
                            }
                        }
                    }
                }
            }
        }

1. Find all pairs of sum c = a + b, a is from the first array and b is from the second array ----- this cost O(N^2);
2. Sort the set which contains all the pair sum using radix sort. It costs O(N^2);
3. Find the common elements between the sorted array in step 2 and the first array or the second array by merging.

for a-b = c:
#include <iostream>
using namespace std;

void getTriple(int *array, int n)
{
for (int i = 0; i < n; ++i)
{
int sum = array[i];
int j = 0;
int k = n - 1;
while (j < k)
{
if (array[j] + array[k] < sum)
{
++j;
}
else if (array[j] + array[k] > sum)
{
--k;
}
else
{
if (i != j && i != k)
{
cout << sum << " " << array[j] << " " << array[k] << endl;
}
++j;
--k;
}
}
}
}

int main()
{
int n;
int array[1000];
cin >> n;
for (int i = 0; i < n; ++i)
{
cin >> array[i];
}
getTriple(array, n);
return 0;
}

for a+b+c=0

#include <iostream>
using namespace std;

void getTriple(int *array, int n)
{
for (int i = 0; i < n; ++i)
{
int sum = -1 * array[i];
int j = i + 1;
int k = n - 1;
while (j < k)
{
if (array[j] + array[k] < sum)
{
++j;
}
else if (array[j] + array[k] > sum)
{
--k;
}
else
{
cout << sum << " " << array[j] << " " << array[k] << endl;
++j;
--k;
}
}
}
}

int main()
{
int n;
int array[1000];
cin >> n;
for (int i = 0; i < n; ++i)
{
cin >> array[i];
}
getTriple(array, n);
return 0;
}