algorithm to find complementary solution to this problem

Question

I had this coding question in an interview.I couldnt find an optimum solution to this. what I did was,

for(i=0;i<n;i++)
for(j=i;j<n;j++)
if(a[i]+a[j]==k) print a[i], a[j]

But that would give rise to a O(n²) complexity. Is there a better way to solve this??

Array A contains n integers. A pair (i,j) of indexes of the array A is called "K-complementary" if A[i]+A[j] = K. For example, given the array:

A[0]=1 A[1]=8 A[2]=-3 A[3]=0 A[4]=1 A[5]=3 A[6]=-2A[7]=4 A[8]=5

The following pairs are 6-complementary: (0,8) (1,6) (4,8) (5,5) (6,1) (8,0) (8,4) For example the pair (4,8) is 6-complementary, because A[4]+A[8] = 1 + 5 = 6.
Write a function

int complementary_pairs(int k,int[] A);

which given an integer K and an array A of n integers, computes the number of K-complimentary pairs of indexes of the array A. For example for array A:

A[0]=1 A[1]=8 A[2]=-3 A[3]=0 A[4]=1 A[5]=3 A[6]=-2A[7]=4 A[8]=5 and K=6 you should return 7

Answer 1

assuming all values are positive, it can be easily extended to case with negatives

loop 1: loop through and add each value to a hash table:

loop 2: loop through and each time check the hash table for K - A[i] if there exists any entries increment a counter for each one.

return the counter/2.

for(i=0;i<n;i++) {
  hash[A[i]]++;
}

counter = 0;
for(i=0;i<n;i++) {
  if (2*A[i] == K) {
    if(hash[K - A[i]] <= 1) continue;
    counter += hash[K - A[i]]-1;
  }
  else counter += hash[K - A[i]];
}
return counter/2;

runtime is O(n)

Answer 2

First, sort the list. This can be O(n) if we have certain constraints on the values, but let's just assume O(n log n). Then for each element x do a binary search for K - x in the list. Add these pairs up and divide by two (since each one is counted twice). Also, there may be other edge cases if duplicate values are permitted in the list.

1 sort list

2 for x in list, find K - x. (binary search)

3 if found increment counter

4 return counter / 2

Answer 3

You can do this in O(NlogN):

Sort the array A which takes O(NlogN).
Next you maintain two index i and j to the first and last element of the array respectively.
Find the sum of elements at index i and j, that is A[i] + A[j] we have 3 cases:

• If that sum is equal to K we have a complementary pair (i,j). See if i and j are different, if yes we also have (j,i) as another complementary pair.
• If that sum is less that K then we need to increase the sum, so increment i.
• If that sum is greater that K then we need to decrease the sum, so decrement j.

Finding complementary pair is O(N), making the entire algorithm O(NlogN)

In Java this can be done as:

int i=0;
int j=arr.length-1;
int count = 0;

while( i <= j ) {
  if( A[i] + A[j] == K ) {
    // (i,j) is a complementary pair.
    count++;

    // if i!= j then (j,i) is also a complementary pair.
    if( i != j) {
       count++;
    }
    i++;
    j--;
  } else if( A[i] + A[j] < K ) {
    i++;
  } else {
    j--;
  }
}

Answer 4

It's possible to do this in O(N), if you have memory to burn. In pseudocode:

Create a radix tree T from A[]  // Performance - O(N)
Set R = 1
for each X in A[]: // Performance - O(N)
    Set Y = K-X
    if Y > X AND T contains Y // Performance - O(1)
        increase R by 1
return R

Some alternatives:

• Use a hashtable instead of a radix tree. Better memory usage, though not a guaranteed O(1) lookup.
• If these are 32-bit integers you can use a bitmask indicating which integers were present. Though it will require 512MB of memory.
• Simply sort the array and then use binary lookup. That will however be a O(N*log(N)) performance. But it can be done with no memory overhead.

Added: Wait, I figured it out! O(N) with very little memory overhead! Check pseudocode:

Sort A[] with radix sort // Performance - O(N)
"Compress A[]" - convert it to an array where every number is just once, but also has a "count" property telling how many times it was in the original A[] // Performance - O(N)
Set B = 0
Set E = length of A[] - 1
Set R = 0
while B <= E:
    set M = A[B].Number + A[E].Number
    if M < K:
        Set B = B + 1
    else if M > K:
        Set E = E - 1
    else:
        if B = E then:
            Set R = R + (A[B].Count*(A[B].Count-1))/2
        else:
            Set R = R + A[B].Count*A[E].Count
        Set B = B + 1
        Set E = E - 1
return R

You can also skip the "compression" part and just calculate the Count on-the-fly, caching the results so that you don't have to do it again, and then using it when increasing A/decreasing B.