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 |