I have to create an O(n log(n)) algorithm that checks if the sum of two numbers in int [] == is the given number.
eg. Given [1,4,7,2,3,4], there will be a sum of 8 (1 + 7), but not 20
This answer suggested a binary sort or merge sort, but they just gave a merge sort algorithm without the logical processing of this particular requirement. Then there was another answer:
Suppose x is the sum we want to check, z is the set of elements from this array: The following algorithm solves the problem:
- Sort items in S.
- Make up the set S = {z: z = x - y for some y ∈ S}.
- Sort items in S.
- If any value in S appears more than once, delete all but one instance. Do the same for S.
- Combine the two sorted sets S and S.
- There are two elements in S whose sum is exactly equal to x if and only if the same value appears in consecutive positions in the combined output.
To substantiate the claim in step 4, we first note that if any value appears twice in the combined output, it must appear in a sequential position. Thus, we can reformulate the condition in step 5, since there are two elements in S whose sum is exactly equal to x if and only if the same value appears twice in the combined output. Suppose some value of w appears twice. Then w appears once in S and once in S. Since w appeared in S, there exists some y ∈ S such that w = x - y or x = w + y. Since w ∈ S, the elements w and y are in S and summed with x.
Conversely, suppose that there exist values w, y ∈ S such that w + y = X. Then, since x - y = w, the value of w appears in S. Thus, w is in both S and S, and therefore it will be displayed twice in the combined output.
Steps 1 and 3 require steps O (n log n). Steps 2, 4, 5, and 6 require O (n). Thus, the total runtime is O (n log n).
But I do not understand what they had in mind. In step 2, what are x and y?
But I created in my own way, interestingly, its O(n log(n)) ?
class FindSum { public static void main(String[] args) { int[] arr = {6,1,2,3,7,12,10,10}; int targetSum = 20; Arrays.sort(arr); System.out.println(Arrays.toString(arr)); int end = arr.length - 1; if (FindSum.binarySearchSum(arr, targetSum, 0, end, 0, end)) { System.out.println("Found!"); } else { System.out.println("Not Found :("); } } public static boolean binarySearchSum(int[] arr, int targetSum, int from1, int end1, int from2, int end2) { // idea is to use 2 "pointers" (simulating 2 arrays) to (binary) search // for target sum int curr1 = from1 + (end1-from1)/2; int curr2 = from2 + (end2-from2)/2; System.out.print(String.format("Looking between %d to %d, %d to %d: %d, %d", from1, end1, from2, end2, curr1, curr2)); int currSum = arr[curr1] + arr[curr2]; System.out.println(". Sum = " + currSum); if (currSum == targetSum) { // base case return true; } else if (currSum > targetSum) { // currSum more than targetSum if (from2 != end2) { // search in lower half of 2nd "array" return FindSum.binarySearchSum(arr, targetSum, from1, end1, from2, curr2 - 1); } else if (from1 != end2) { // search in lower half of 1st "array" (resetting the start2, end2 args) return FindSum.binarySearchSum(arr, targetSum, from1, curr1 - 1, 0, arr.length - 1); } else { // can't find return false; } } else { // currSum < targetSum if (from2 != end2) { // search in upper half of 2nd "array" return FindSum.binarySearchSum(arr, targetSum, from1, end1, curr2 + 1, end2); } else if (from1 != end2) { // search in upper half of 1st "array" (resetting the start2, end2 args) return FindSum.binarySearchSum(arr, targetSum, curr1 + 1, end1, 0, arr.length - 1); } else { // can't find return false; } } } }