CareerCup

Method 1: Sort the array and then do the following (O(n log n)):

p=0,q=n-1;
while(p<q)
{
  if(a[p]+a[q]==k)
  {
      cout<<a[p]<<"\t"<<a[q];
      p++;
      q--;
   }
   else if(a[p]+a[q]>k)
      q--;
   else 
      p++;
}

Method 2: We can use hash table (O(n)):

for(i=0;i<n;i++)
{
   Complement=K-a[i];
   HashTable[a[i]]=i;
   if(SearchHashTable(Complement)!=-1)
     cout<<"Indices:\t"<<HashTable[Complement]<<"\t"<<i<<endl;
}

O(N):

boolean exists(int[] arr, int k) {
// Transfer into HashSet and taking into account duplicates
	Set<Integer> set = new HashSet<Integer>();
	for (int c : arr) {
		if (set.contains(c))
			if (c*2 == k) return true;
		set.add(c);
	}
// Now that all duplicates have been accounted for, do a simple search and match
	for (int c : set) {
		if (set.contains(k-c)) return true;
	}
	return false;
}

Can you elaborate more on "randomly sorted"? Perhaps also give an example.

1. NlogN to sort (from smallest to largest), then two indices: i=0, j=N; if A(i)+A(j) > k, j--; if(A(i)+A(j) < k) i++
2. bucket sort?

from collections import defaultdict

def check(a):
    #a = [...] # array
    n = len(a) 
    h = defaultdict(int)
    for i in range(n):
        h[a[i]] += 1
    for i in range(n):
        d = k - h[a[i]]
        if (h[d] > 0) return True
    return False

If we know about the range (max value of elements) than we use redix sort and than use first approach of Anonymous .

O(N) -- two pointer one at starting and one at end
i=0;
j=a.length
if a[i]+a[j]==NUM
return a[i] and a[j]
if a[i]+a[j]>NUM
j--
else
i++

O(NLOGN)
for each a[i]
do binary search in the sorted array to find the othe number which makes up the sum

int diff = k - a[i] // where i is an index of the array
Then find element equals to 'diff' in array except index i
This gives a O(n) solution, right?

-(BOOL)checkSumInArray:(NSArray *)myArray isEqualTo:(NSInteger)k{
    int front = 0;
    int back = [myArray count]-1;
    BOOL result = NO;
    //sort array
    [myArray sortedArrayUsingSelector: @selector(compare:)];
    while (front < back) {
        NSInteger sum = [myArray[front] integerValue] + [myArray[back] integerValue];
        if (sum == k) {
            result = YES;
            break;
        }
        else if (sum > k){
            back--;
            continue;
        }
        else{
            front++;
            continue;
        }
    }
    return result;
    
}

O(N logN):

static bool IsExistsPairThatThierSumIsK(int[] a, int k)
{
    for (int i = 0; i < a.Length; i++)
    {
        int j = FindLeftmost(a, k - a[i]);
        
        if (j == -1) continue;
        
        if (i != j || (i + 1 < a.Length && a[i] == a[i + 1])) return true;
    }
    
    return false;
}

static int FindLeftmost(int[] a, int k)
{
    int l = 0;
    int r = a.Length - 1;
    
    while (l < r)
    {
        int m = l + (r - l) / 2;
        
        if (a[m] >= k) r = m;
        else l = m + 1;
    }
    
    return a[l] == k ? l : -1;
}

O(N):

static bool IsExistsPairThatThierSumIsK2(int[] a, int k)
{
    int l = 0;
    int r = a.Length - 1;
    
    while (l < r)
    {
        if (a[l] + a[r] == k) return true;
        else if (a[l] + a[r] > k) r--;
        else l++;
    }
    
    return false;
}

import java.util.HashSet;
import java.util.Set;
public class TwoNumSum {
	public static void main(String[] args) { 
		int sum = 20;
		int [] nums = {1,4,5, 16, 17, 20};
		for(int i : twoNumSum(sum, nums))
			System.out.print(i + "\t");
	}
	public static int[] twoNumSum(int sum, int [] nums){
		//This is O(n) algorithm. 
		int [] r  = new int[2];
		Set <Integer> hs = new HashSet<Integer>();
		for(Integer intg: nums )
			hs.add(intg); 
		
		for(Integer intg: nums ){
			if (hs.contains(sum - intg)){
				r[0] = intg;
				r[1] = sum -intg;
			}
		}
		return r;
	}
}

int sum_pair_n(const int *i, const int size, const int sum)
{
	int tail = size - 1;
	int head = 0;
	int iSum;

	while(head < tail)
	{
		iSum = i[head] + i[tail];
		if(iSum == sum)
		{
			return 1;
		}
		else if(iSum < sum)
		{
			head++;
		}
		else if(iSum > sum)
		{
			tail--;
		}
	}
	return 0;
}

int sum_pair_logn(const int *i, const int size, const int sum)
{
	int head = 0;
	int look_for;

	while(head < size)
	{
		look_for = sum - i[head];
		int h=head+1, t=size;
		while(h<=t)
		{
			if(i[(h+t)/2] == look_for)
			{
				return 1;
			}
			else if(i[(h+t)/2] > look_for) t = (h+t)/2 - 1;
			else if(i[(h+t)/2] < look_for) h = (h+t)/2 + 1;
		}
		head++;
	}
	return 0;
}

int main()
{
	int i[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
	printf("%d\n", sum_pair_n(i, 10, 5));
	printf("%d\n", sum_pair_logn(i, 10, 4));
	return 0;
}

1. Sorting the array in (NlogN) and then find out the pair in (logN) by using binary search.
2. Divide n Conquer would go.