Google Answers Logo
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.
Answer  
There is no answer at this time.

Comments  
Subject: Re: finding a sum of 2 integers in an array
From: manuka-ga on 27 Oct 2005 23:54 PDT
 
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).
Subject: Re: finding a sum of 2 integers in an array
From: bighugegamer-ga on 28 Oct 2005 13:15 PDT
 
#include <iostream>
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<n;i++, j--)
	{
		B[j]=A[i]-x;
	}
	for (i=0;i<n;i++)
	{
		if (A[i]==B[i])
		{
			//answer is true
			delete [] B;
			cout<<endl<<"There are two numbers in array with sum = "<<x<<endl;
			return (1);
		}
	}

	delete [] B;
	cout<<endl<<"There are no two numbers in array with sum = "<<x<<endl;
	return (0);
}
Subject: Re: finding a sum of 2 integers in an array
From: mathtalk-ga on 29 Oct 2005 07:50 PDT
 
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

Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service.

If you feel that you have found inappropriate content, please let us know by emailing us at answers-support@google.com with the question ID listed above. Thank you.
Search Google Answers for
Google Answers  


Google Home - Answers FAQ - Terms of Service - Privacy Policy