Taken from Introduction to Algorithms
Describe a Θ(n lg n)-time algorithm that, given a set S of n integers and another integer x, determines whether or not there exist two elements in S whose sum is exactly x.
This is my best solution implemented in Java so far:
public static boolean test(int[] a, int val) {
mergeSort(a);
for (int i = 0; i < a.length - 1; ++i) {
int diff = (val >= a[i]) ? val - a[i] : a[i] - val;
if (Arrays.binarySearch(a, i, a.length, diff) >= 0) {
return true;
}
}
return false;
}
Now my 1st question is: Is this a correct solution? From my understanding, mergeSort should perform the sort in O(n lg n), the loop should take O(n lg n) (n for the iteration multiplied by O(lg n) for the binary search, resulting in O(2n lg n), so it should be correct.
My 2nd question is: Are there any better solutions? Is sorting the array essential?
Follow the steps below to solve the given problem: Initialize the count variable with 0 which stores the result. Iterate arr and if the sum of ith and jth [i + 1…..n – 1] element is equal to sum i.e. arr[i] + arr[j] == sum, then increment the count variable. Return the count.
C program to find a pair of number whose sum is K using hash table. Sort inputArray using any O(nLogn) time sorting algorithm. Initialize leftIndex and rightIndex to 0 and N-1 respectively. If inputArray[leftIndex] + inputArray[rightIndex] is equal to K, then we found a pair.
Your solution seems fine. Yes you need to sort because its a pre requisite for binary search. You can make a slight modification to your logic as follows:
public static boolean test(int[] a, int val) { Arrays.sort(a); int i = 0; // index of first element. int j = a.length - 1; // index of last element. while(i<j) { // check if the sum of elements at index i and j equals val, if yes we are done. if(a[i]+a[j] == val) return true; // else if sum if more than val, decrease the sum. else if(a[i]+a[j] > val) j--; // else if sum is less than val, increase the sum. else i++; } // failed to find any such pair..return false. return false; }
There's another very fast solution: Imagine you have to solve this problem in Java for about 1 billions integers. You know that in Java integers go from -2**31+1
to +2**31
.
Create an array with 2**32
billion bit (500 MB, trivial to do on today's hardware).
Iterate over your set: if you have an integer, set corresponding bit to 1.
O(n) so far.
Iterate again over your set: for each value, check if you have a bit set at "current val - x".
If you have one, you return true.
Granted, it needs 500 MB of memory.
But this shall run around any other O(n log n) solution if you have, say, to solve that problem with 1 billion integers.
O(n).
This is correct; your algorithm will run in O(n lg n) time.
There is a better solution: your logic for calculating diff is incorrect. Regardless of whether a[i]
is greater than or less than val
, you still need diff to be val - a[i]
.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With