Given an array of size n and a number X, you are supposed to find a pair of numbers that sums to X.

This problem is quite largely discussed and is very famous for its various ways to attack. This can be constrained in time and in space. The most primitive way of attacking this problem would yield an solution that runs in O(n2) time.
Let me define the problem clearly. Given an array of size n and a number X, you are supposed to find a pair of numbers that sums to X. Only one pair would be enough.
Lets see how we can find the solution for this in O(n) using a HashSet. Yes, HashSet is a costly data structure to use, but lets consider this primitive just due to the linear order it provides.


import java.util.HashSet;
import java.util.Set;

public class FindSumHashSet {
public static void main(String a[]){
FindSumHashSet sumFinder = new FindSumHashSet();
sumFinder.begin();
}

public void begin(){
int[] sampleArray = getRandomArray(20);
int randomSum = sampleArray[15] + sampleArray[10];
System.out.print("ARRAY : ");
for(int i:sampleArray){
System.out.print(i+" ");
}
System.out.println();
findPair(sampleArray,randomSum);
}

public void findPair(int[] sampleArray, int randomSum) {
Set sampleArraySet = new HashSet();
for(int i=0;i sampleArraySet.add(sampleArray[i]);
int valueToFind = randomSum - sampleArray[i];
if(sampleArraySet.contains(valueToFind)){
System.out.println("SUM : "+randomSum);
System.out.println("PAIR : "+valueToFind+","+sampleArray[i]);
break;
}
}
}

private int[] getRandomArray(int size) {
int[] randomArray = new int[size];
for(int i=0;i randomArray[i] = (int)(Math.random()*10);
}
return randomArray;
}
}
//SAMPLE OUTPUTS

//ARRAY : 7 3 6 4 3 4 7 7 5 1 4 6 2 4 1 7 5 8 9 7
//SUM : 11
//PAIR : 7,4

//ARRAY : 0 2 9 6 0 7 6 5 1 7 9 0 7 1 2 4 4 3 9 0
//SUM : 13
//PAIR : 6,7