CareerCup

Doubt there is a known algorithm for NlogN time?

I think this problem can be reduced to 3SUM in both directions, and there is nothing sub quadratic known for 3SUM.

You can store the values of the first array in a HashMap, recursively break down the second array and for each element in the second array, search linearly in the third array.

a = k - b - c

Check if a exists in the HashMap.

import java.util.*;

public class SumOfThree {

   static boolean isSumInC(int val, int[] c, int k, HashMap<Integer, Integer> hash){
	   for(int i=0;i<c.length;i++)
	    {int rem = k - val - c[i];
	     if(hash.containsValue(rem))
	    	 return true;
		}
	   
	   return false;
	   
   }
	
   static boolean divideb(int[] b, int st, int end, int[] c, int k, HashMap<Integer, Integer> hash){
	   if(st==end)
		  return isSumInC(b[st], c, k, hash);
	   else{
		   int mid = (st+end)/2;
		   return divideb(b, st, mid, c, k, hash) || divideb(b, mid+1, end, c, k, hash); 
	   }
	   
   }
	
   static boolean isSumOfThree(int[] a, int[] b, int[] c, int k){
	   HashMap<Integer, Integer> hash = new HashMap<Integer, Integer>();
	   
	   for(int i=0;i<a.length;i++)
		   hash.put(i,  a[i]);
	   
	   return divideb(b, 0, b.length-1, c, k, hash);
	   
   }
	
   public static void main(String args[]){
	  int[] a = {30, 20, 5, 10};
	  int[] b = {5, 12, 18, 20};
	  int[] c = {7, 10, 12, 20};
	  
	  int k = 27;
	  
	  boolean result = isSumOfThree(a, b, c, k);
	  System.out.println(result);
		
	}
}

The good ole slow O(n*n) time solution.

public static boolean abcSum(int a[], int b[], int c[], int k){
		HashSet<Integer> bcCombos = new HashSet<Integer>();
		for (int i = 0; i < b.length; i++){
			for (int j = 0; j < c.length; j++){
				bcCombos.add(b[i]+c[j]);
			}
		}
		for (int i = 0; i < a.length; i++){
			if (bcCombos.contains(k-a[i])) return true;
		}
		return false;
	}

1 Firat Sort all the strings then
2.1) If x, y and z are same, we can simply print any of them as common element and move ahead in all three arrays.
2.2) Else If x < y, we can move ahead in ar1[] as x cannot be a common element 3) Else If y < z, we can move ahead in ar2[] as y cannot be a common element 4) Else (We reach here when x > y and y > z), we can simply move ahead in ar3[] as z cannot be a common element.

1 First Sort the arrays.
2.1) If x, y and z are same, we can simply print any of them as common element and move ahead in all three arrays.
2.2) Else If x < y, we can move ahead in ar1[] as x cannot be a common element 3) Else If y < z, we can move ahead in ar2[] as y cannot be a common element 4) Else (We reach here when x > y and y > z), we can simply move ahead in ar3[] as z cannot be a common element.

Sort all three arrays, then sequentially scan them to find the triplet. In the second phase, you have a pointer to each of the 3 arrays, call it i1, i2, i3 for A, B, C. If A[i1]+B[i2]+C[i3]==k return true. Otherwise, move the index to the next smallest element and so on.
Cost of sorting: O(N*log(N)), cost of second phase is O(N)