CareerCup

There are two methods to accomplish this:

First one is O(Nlog(N)) time and O(1) space: Sort the Array, initialize two indexes one at the start and the other at the end of the array. If the sum of the two elements are greater than the target value, decrease the 'end' index by 1, otherwise increase the 'start' index by 1. If you find the sum, return it, if the indexes cross over and you still haven't found the sum, return false.

Second method is O(N) time and O(N) space: Put all elements in Hashmap, then loop through the array once again and check if the Hashmap contains (target - element).

The best would be to explain both solutions and the time/space tradeoff for each.

1 #include <stdio.h>                                                         
  2 #include <iostream>                                                        
  3 #include <vector>                                                          
  4 #include <algorithm>                                                       
  5 using namespace std;                                                       
  6                                                                            
  7 int X = 4;                                                                 
  8 int ary[] = {2,1,3,4,8,11,-13,17,19,41,71,32,29};                          
  9 vector<int> input;                                                         
 10                                                                            
 11 int main()                                                                 
 12 {                                                                          
 13     input.assign(&ary[0], &ary[0] + sizeof(ary)/sizeof(int));              
 14     sort(input.begin(), input.end());                                      
 15     if(input[0] < 0)                                                       
 16     {                                                                      
 17         int offset = -input[0];                                            
 18         X += offset;                                                       
 19         for(int i=0; i<input.size(); ++i)                                  
 20             input[i] += offset;                                            
 21     }                                                                      
 22                                                                            
  21     }                                                                     
 22                                                                            
 23     int h = 0;                                                             
 24     int t = input.size() - 1;                                              
 25     bool result = false;                                                   
 26     while(t > h)                                                           
 27     {                                                                      
 28         if(input[h] + input[t] == X)                                       
 29         {                                                                  
 30             result = true;                                                 
 31             break;                                                         
 32         }                                                                  
 33         else if( input[h] + input[t] < X)                                  
 34             h++;                                                           
 35         else if( input[h] + input[t] > X)                                  
 36             t--;                                                           
 37     }                                                                      
 38                                                                            
 39     printf("%d - x:%d y:%d\n", result, input[h], input[t]);                
 40     return 0;                                                              
 41 }

bool search(int *arr,int a, int start, int end)
{
	if(start >=end)
		return false;
	if(arr[start] == a)
		return true;
	int mid = (start + end)/2;
	if(arr[mid]==a)
		return true;
	if (arr[mid]<a)
		return search(arr,a,mid+1,end);
	else
		return search(arr,a,start,mid-1);
}
bool findDiff(vector<int> arr, int X)
{
	for(int i=0;i<arr.size(); i++)
	{
		int diff = X-arr[i];
		if(search(arr,diff,i+1,arr.size-1))
			return true;			
	}
	return false;
}

public boolean hasSummy(int [] arr, int value) {
    //Returns true iff there are x & y such  that value = x +y
    Arrays.sort(arr);
    
    for (int i: arr) {
      int toSearch = value -i;
      if(Arrays.binarySearch(arr, toSearch) >0) {
        System.out.println(toSearch +" " + i);
        return true;
      }
    }
    return false;
    
  }