locate a pair with targetDdiff==55

http://www.geeksforgeeks.org/write-a-c-program-that-given-a-set-a-of-n-numbers-and-another-number-x-determines-whether-or-not-there-exist-two-elements-in-s-whose-sum-is-exactly-x/ has a nice algo for “sum=55”

This technique becomes more interesting when the problem is modified to “find a pair whose difference is 55”. Without loss of generality, let’s keep everything positive.

–my solution:

  1. sort the original integers
  2. duplicate the array, flip the signs and reverse it
  3. append positive array to get a combined, sorted array, whose left half are all negavie
  4. now start the 2 pointers, but each constrained within its half.
//Requirement: find all pairs in the array whose difference = D
//
//If there are negative numbers, then the simplest solution is
//to shift everything up to positive

vector<int> v{3,1,1,7,4,9};
int const SZ = v.size();
int const D = 2;

void dump(){
  for(int i=0; i<v.size(); ++i) cout<<setw(3)<<v[i];
  cout<<endl;
  for(int i=0; i<v.size(); ++i) cout<<setw(3)<<i;
  cout<<endl;
}
int main(){
  sort(v.rbegin(), v.rend());
  for (int i=SZ-1; i>=0; --i) v.push_back(-1 * v[i]);
  dump();
  for(int left=0, right=v.size()-1; left < SZ && right>=SZ;){
        int diff = v[left] + v[right];
        if (diff == D) {
                cout<<v[left]<<" - "<<-1*v[right]<<endl;
                if (v[left+1] == v[left]) ++left;
                else --right;
        }
        else if (diff < D) --right;
        else ++left;
  }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s