Advertisement
Advertisement


Find a pair of elements from an array whose sum equals a given number


Question

Given array of n integers and given a number X, find all the unique pairs of elements (a,b), whose summation is equal to X.

The following is my solution, it is O(nLog(n)+n), but I am not sure whether or not it is optimal.

int main(void)
{
    int arr [10] = {1,2,3,4,5,6,7,8,9,0};
    findpair(arr, 10, 7);
}
void findpair(int arr[], int len, int sum)
{
    std::sort(arr, arr+len);
    int i = 0;
    int j = len -1;
    while( i < j){
        while((arr[i] + arr[j]) <= sum && i < j)
        {
            if((arr[i] + arr[j]) == sum)
                cout << "(" << arr[i] << "," << arr[j] << ")" << endl;
            i++;
        }
        j--;
        while((arr[i] + arr[j]) >= sum && i < j)
        {
            if((arr[i] + arr[j]) == sum)
                cout << "(" << arr[i] << "," << arr[j] << ")" << endl;
            j--;
        }
    }
}
2017/08/21
1
123
8/21/2017 12:42:32 AM

Accepted Answer

# Let arr be the given array.
# And K be the give sum


for i=0 to arr.length - 1 do
  hash(arr[i]) = i  // key is the element and value is its index.
end-for

for i=0 to arr.length - 1 do
  if hash(K - arr[i]) != i  // if Kth element exists and it's different then we found a pair
    print "pair i , hash(K - arr[i]) has sum K"
  end-if
end-for
2019/08/24
135
8/24/2019 7:55:35 AM


Implementation in Java : Using codaddict's algorithm (Maybe slightly different)

import java.util.HashMap;

public class ArrayPairSum {


public static void main(String[] args) {        

    int []a = {2,45,7,3,5,1,8,9};
    printSumPairs(a,10);        

}


public static void printSumPairs(int []input, int k){
    Map<Integer, Integer> pairs = new HashMap<Integer, Integer>();

    for(int i=0;i<input.length;i++){

        if(pairs.containsKey(input[i]))
            System.out.println(input[i] +", "+ pairs.get(input[i]));
        else
            pairs.put(k-input[i], input[i]);
    }

}
}

For input = {2,45,7,3,5,1,8,9} and if Sum is 10

Output pairs:

3,7 
8,2
9,1

Some notes about the solution :

  • We iterate only once through the array --> O(n) time
  • Insertion and lookup time in Hash is O(1).
  • Overall time is O(n), although it uses extra space in terms of hash.
2015/10/28

Solution in java. You can add all the String elements to an ArrayList of strings and return the list. Here I am just printing it out.

void numberPairsForSum(int[] array, int sum) {
    HashSet<Integer> set = new HashSet<Integer>();
    for (int num : array) {
        if (set.contains(sum - num)) {
            String s = num + ", " + (sum - num) + " add up to " + sum;
            System.out.println(s);
        }
        set.add(num);
    }
}
2014/12/01

Python Implementation:

import itertools
list = [1, 1, 2, 3, 4, 5,]
uniquelist = set(list)
targetsum = 5
for n in itertools.combinations(uniquelist, 2):
    if n[0] + n[1] == targetsum:
        print str(n[0]) + " + " + str(n[1])

Output:

1 + 4
2 + 3
2015/12/07

C++11, run time complexity O(n):

#include <vector>
#include <unordered_map>
#include <utility>

std::vector<std::pair<int, int>> FindPairsForSum(
        const std::vector<int>& data, const int& sum)
{
    std::unordered_map<int, size_t> umap;
    std::vector<std::pair<int, int>> result;
    for (size_t i = 0; i < data.size(); ++i)
    {
        if (0 < umap.count(sum - data[i]))
        {
            size_t j = umap[sum - data[i]];
            result.push_back({data[i], data[j]});
        }
        else
        {
            umap[data[i]] = i;
        }
    }

    return result;
}
2016/03/30

Here is a solution witch takes into account duplicate entries. It is written in javascript and assumes array is sorted. The solution runs in O(n) time and does not use any extra memory aside from variable.

var count_pairs = function(_arr,x) {
  if(!x) x = 0;
  var pairs = 0;
  var i = 0;
  var k = _arr.length-1;
  if((k+1)<2) return pairs;
  var halfX = x/2; 
  while(i<k) {
    var curK = _arr[k];
    var curI = _arr[i];
    var pairsThisLoop = 0;
    if(curK+curI==x) {
      // if midpoint and equal find combinations
      if(curK==curI) {
        var comb = 1;
        while(--k>=i) pairs+=(comb++);
        break;
      }
      // count pair and k duplicates
      pairsThisLoop++;
      while(_arr[--k]==curK) pairsThisLoop++;
      // add k side pairs to running total for every i side pair found
      pairs+=pairsThisLoop;
      while(_arr[++i]==curI) pairs+=pairsThisLoop;
    } else {
      // if we are at a mid point
      if(curK==curI) break;
      var distK = Math.abs(halfX-curK);
      var distI = Math.abs(halfX-curI);
      if(distI > distK) while(_arr[++i]==curI);
      else while(_arr[--k]==curK);
    }
  }
  return pairs;
}

I solved this during an interview for a large corporation. They took it but not me. So here it is for everyone.

Start at both side of the array and slowly work your way inwards making sure to count duplicates if they exist.

It only counts pairs but can be reworked to

  • find the pairs
  • find pairs < x
  • find pairs > x

Enjoy!

2013/03/29

Source: https://stackoverflow.com/questions/4720271
Licensed under: CC-BY-SA with attribution
Not affiliated with: Stack Overflow
Email: [email protected]