CareerCup

what if we do not need to merge the sorted arrays ?
that is, sort B and C, then for each element of A check if A[i] == B[j] + C[k]
using standard approach. Complexity: O(n^2)

void find_sum(int *a, int *b, int *c, int n) {
    // check if a == b + c
    for(int i = 0; i < n; i++) {
        int x = a[i];
        int l = 0, r = n - 1;
        for(; ;) {
            int s = b[l] + c[r];
            if(s == x) {
                printf("%d = %d + %d\n", x, b[l], c[r]);
                l++;
            } else if(s < x) {
                l++;
            } else
                r--;
            if(l == n || r == -1)
                break;
        }
    }
    printf("brute force check:\n");
    for(int i = 0; i < n; i++) {
        int x = a[i];
        for(int j = 0; j < n; j++) {
            for(int k = 0; k < n; k++) {
                if(x == b[j] + c[k]) {
                    printf("all: %d = %d + %d\n", x, b[j], c[k]);
                }
            }
        }
    }
}

int main() {
    int a[] = {8, 9, 10, 11, 20, 22};
    int b[] = {1, 5, 6, 6, 9, 11};
    int c[] = {3, 4, 7, 11, 12, 15};
    int n = sizeof(a) / sizeof(int);

    find_sum(a, b, c, n);
    return 1;
}

output:
8 = 1 + 7
8 = 5 + 3
9 = 5 + 4
9 = 6 + 3
9 = 6 + 3
10 = 6 + 4
10 = 6 + 4
20 = 5 + 15
20 = 9 + 11
22 = 11 + 11
brute force check:
all: 8 = 1 + 7
all: 8 = 5 + 3
all: 9 = 5 + 4
all: 9 = 6 + 3
all: 9 = 6 + 3
all: 10 = 6 + 4
all: 10 = 6 + 4
all: 20 = 5 + 15
all: 20 = 9 + 11
all: 22 = 11 + 11

yes I said that. But asked to solve it without hashing.

Use hashing

The question didn't say a,b,c has to be have same index, which mean it can be any combination. So your merging from B and C to D will take n^2 time, and D array will be size of B*C. I don't think this is appropriate.

@Puru:
There is no need to merge it. Just sort B & C: (Both A & B are in ascending order now).

Now for every a belongs to A, search element say b in B and say c in C whose some is equal to a.

keep in mind that start the search from End of B and C and see if the sum of b & c is greater than a then fall back to element that just smaller element from just previous elements in B & C.

O(n) = nlogn+n*n

i think we cant merge nay of the arrays becoz a b and c has to be from different array , and if we merge the we 2 number could be from same array.

n^3 and n^2logn solution is obvious.

i think instead of adding b+c to create d, we can create array d=a-b.. thus saving some ammount of memory.

i think instead of adding b+c to create d, we can create array d=a-b.. thus saving some ammount of memory.

a - b = c
So a = b + c
Sort B and C in decreasing order.
Then create a 2-D array D where D[i][j] = B[i] + C[j];
This 2-D array has all the rows in descending order and all cols also in descending order. Now do a zizag search in O(N) time for each value in A in D.


int a[] = {8, 9, 10, 11, 20, 22};
int b[] = {1, 5, 6, 6, 9, 11};
int c[] = {3, 4, 7, 11, 12, 15};

sorted b = 11,9,6,6,5,1 <-- O(nlgn)
sorted c = 15,12,11,7,4,3 <-- O(nlgn)
D = 26,23,22,18,15,14
24,21,20,16,13,12
21,18,17,13,10,09
21,18,17,13,10,09
20,17,16,12,09,08
16,13,12,08,05,04

Now in this 2-D array search each element of A in O(N) time.

A -> length a
B -> length b
C -> length c

Sort only C -> O(clogc)

for ( i : 0 -> a){
for (j : 0 -> b) {
searchInC(A[i] - B[j]); //binary search
print if found;
}
}

Total complexity

O(ablogc + clogc)
O((ab + c)logc)

Though not best of the approaches!

solution complexity: o(nlogn) were n is the size of the longest array.
1. sort all 3 arrays.
2. The range of C is [C[1] .. C[n]]
3. have two pointers to the end of A and B.
4. each time subtract pointer to B from pointer to A: if out of C range (from 3) : if less than range reduce pointer to B by 1. if bigger than range than reduce pointer to A by one. if In range of C hash the pair (A,B) according to the result A - B.
5. Go trough all elements of C and search them in the hash. if they exist, print the tuple (A,B,C).

In order to find a pair (a, b) (s.t. a is in A, b is in B) whose sums equals x, we would :
a. Sort A, B (O(nlogn))
b. initialize i, j with
i = A[0]
j = B[n] (Assuming size of all arrays is same, n)
Then:
a. If A[i]+B[j] < x , increment i
b. If A[i]+B[j] > x, dec j
c. If A[i]+B[j] == x, print A[i], B[j]
This takes O(n).

So total time complexity is O(nlogn) and space complexity is O(1)

Now we can easily extend this approach to this qs by :

Sort A,B : O(nlogn)
For each k in C
Find if there exists a pair, (a, b) s.t. a+b = k

Now the complexity of the algo is O(nlogn)+O(n^2) = O(n^2).

a-b = c implies a = b + c

Sort B and C in place O(n log n)

Now merge B and C into D

Define a function Search that searches for indices in D whose sum is a given number.

bool Search (int[] D, int x, out int i, out int j)
{
   if ((D == null) || (D.length < 2))
   {
       return false;
   }

   i = 0;
   j = D.length - 1;

   while (i < j)
   {
      int sum = D[i] + D[j];
      if (sum == x)
      {
          return true;
      }
      else if (sum < x)
      {
          i++;
      }
      else
      {
          j--;
      }
   }

   return false;
}

For each element of A, if Search returns true, then look for D[i] in C and D[j] in D using binary search and also D[j] in C and D[i] in D also using binary search if first search yields false. If found print the tuple.

The complexity is O(nlogn) for sorting, O(n) for merging. Then for each element of A, it will take O(n) search. Hence O(n^2) in total. Hashing can reduce this to O(nlogn).

Sort B and C, it takes O(n logn) and now add B and C and create another array D of size n^2, O(n^2). Apply binary search in that array for each element in A each element:2*log n, O(n logn),So total complexity would be O(n^2).

SumArray(int A[], int B[], int C[], int a, int b, int c){
if ( a== Length(A) || b== Length(B) || c== Length(C) ) return;
if ( A[a] == B[b] + C[c]) print A[a],B[b],C[c];
else{
SumArray(A, B, C, a+1, b, c);
SumArray(A, B, C, a, b+1, c);
SumArray(A, B, C, a, b, c+1);
}
}

// complexity (n^3) - without doing sorting O(1)
// Above algo can be improved to n^2 using memory (n*n)