Menu
Given an integer x and a sorted array a of N distinct integers, design a linear-time algorithm to determine if there exists two distinct indices i and j such that a[i] + a[j] == x
537
An algorithm is said to take linear time, or time, if its time complexity is . Informally, this means that the running time increases at most linearly with the size of the input. More precisely, this means that there is a constant c such that the running time is at most. for every input of size n.
The two-sum problem is a question that asks that if given an array of integers (numbers), like [1, 2, 3], and a target sum number, such as 5, return an array of elements that add up to that target sum number. If no two numbers in the array add up to the target number, then we need to return an empty array; [].
This is type of Subset sum problem
Here is my solution. I don't know if it was known earlier or not. Imagine 3D plot of function of two variables i and j:
sum(i,j) = a[i]+a[j] For every i there is such j that a[i]+a[j] is closest to x. All these (i,j) pairs form closest-to-x line. We just need to walk along this line and look for a[i]+a[j] == x:
int i = 0; int j = lower_bound(a.begin(), a.end(), x) - a.begin(); while (j >= 0 && j < a.size() && i < a.size()) { int sum = a[i]+a[j]; if (sum == x) { cout << "found: " << i << " " << j << endl; return; } if (sum > x) j--; else i++; if (i > j) break; } cout << " not found\n"; Complexity: O(n)
181
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
