View Question
Q: finding a sum of 2 integers in an array ( No Answer,   3 Comments )
 Question
 Subject: finding a sum of 2 integers in an array Category: Computers > Algorithms Asked by: semsem66-ga List Price: \$2.50 Posted: 27 Oct 2005 19:58 PDT Expires: 26 Nov 2005 18:58 PST Question ID: 585887
 ```Given an array A of n integers, in sorted order, and an integer x. design an O(n)-time complexity algorithm to determine whether there are 2 integers in A whose sum is exactly x.```
 There is no answer at this time.

 ```This looks pretty simple. You need two pointers to the array; start one at the beginning and one at the end. I'm assuming the integers are stored in ascending order; the modifications for descending order should be pretty clear. 1. Get value at start pointer, call it s. 2. Get value at end pointer, call it e. 3a. If e is equal to x - s, return success. 3b. If e is greater than x - s, decrement the end pointer. If end pointer is before start pointer, return failure; else go to 2. 3c. If e is less than x - s, increment the start pointer. If start pointer is after end pointer, return failure; else go to 1. Basically we're being smart about which potential partners we look at for each candidate. At each iteration we narrow the gap between start and end pointers by 1, so we execute n iterations at most and we don't have an interior loop, so it's O(n).```
 ```#include using namespace std; int solve (int A[], int n, int x); int main() { int A[]={1,2,3,4,5,6,7,8,9,10}; int x= 5; solve(A,10,x); x=232; solve (A,10,x); } int solve (int A[], int n, int x) { int *B; int i,j; B=new int[n]; for (i=0, j=n-1 ;i
 ```There is a little ambiguity in the problem formulation, because "determine whether there are 2 integers in A whose sum is exactly x" might mean that we seek two distinct integers and that it is forbidden to use the same integer twice. I'd ask the instructor to clarify which interpretation was intended. Assuming the same entry can be used twice, manuka-ga's analysis is correct. Rather than check all n*(n+1)/2 possible pairs, manuka-ga's approach is "adaptive" and uses information from the "failure" of previous steps to prune the search space down to O(n). Also, the logic is easily revised, should the instructor say that the same entry cannot be used twice. If I'm interpreting bighugegamer-ga's code correctly (and acknowledging that the indexing there is C-style/zero-based), B[i] is assigned value A[n-i-1] - x. It then checks whether for some index i: A[i] == B[i], equiv. A[i] == A[n-i-1] - x This doesn't give a way of expressing x as the sum of two entries in A, but if B[i] were instead assigned x - A[n-i-1], then: A[i] == B[i] implies A[i] == x - A[n-i-1] and within the limitations of computer arithmetic, x is A[i] + A[n-i-1]. While this would at least give a possibility to find a solution, those are not the only candidates that need to be checked. For example, x might be expressible, to use the n = 5 test case, as A[3] + A[4]. A picture might be helpful. Consider the n-by-n array of all possible sums of pairs from array A: A[1] + A[1] ... A[1] + A[j] ... A[1] + A[n] ... ... ... A[i] + A[1] ... A[i] + A[j] ... A[i] + A[n] ... ... ... A[n] + A[1] ... A[n] + A[j] ... A[n] + A[n] bighugegamer-ga's code roughly does a search across only one of the anti-diagonals, potentially overlooking solutions. manuka-ga's strategy overcomes that kind of limitation by making a zig-zag search pattern. Essentially manuka-ga's search starts at one of the "outside" corners (since addition is commutative, the matrix above is symmetric and only half of it needs to be searched). Both the rows and the columns of this matrix are in sorted order (ascending, for the sake of discussion). The search strategy outlined by manuka-ga says, if the currently search entry is equal to x, we're done. Otherwise, decrease the row if we are too high or increase the column if we are too low. Stop with "failure" if this movement would take us out of the matrix (or across the main diagonal, by symmetry). regards, mathtalk-ga```