find pair of numbers in array that add to given su

Question

Question: Given an unsorted array of positive integers, is it possible to find a pair of integers from that array that sum up to a given sum?

Constraints: This should be done in O(n) and in-place (without any external storage like arrays, hash-maps) (you can use extra variables/pointers)

If this is not possible, can there be a proof given for the same?

Answer 1

The following site gives a simple solution using hashset that sees a number and then searches the hashset for given sum-current number http://www.dsalgo.com/UnsortedTwoSumToK.php

Answer 2

First you should find reverse array => sum minus actual array then check whether any element from these new array exist in the actual array.

const arr = [0, 1, 2, 6];

const sum = 8;

let isPairExist = arr
  .map(item => sum - item) // [8, 7, 6, 2];
  .find((item, index) => {
    arr.splice(0, 1); // an element should pair with another element
    return arr.find(x => x === item);
  })
  ? true : false;

console.log(isPairExist);

Answer 3

Not guaranteed to be possible; how is the given sum selected?

Example: unsorted array of integers

2, 6, 4, 8, 12, 10

Given sum:

7

??

Answer 4

def pair_sum(arr,k):
    counter = 0
    lookup = set()
    for num in arr:
        if k-num in lookup:
            counter+=1
        else:
            lookup.add(num)
    return counter
    pass
pair_sum([1,3,2,2],4)

The solution in python

Answer 5

This might be possible if the array contains numbers, the upper limit of which is known to you beforehand. Then use counting sort or radix sort(o(n)) and use the algorithm which @PengOne suggested.

Otherwise I can't think of O(n) solution.But O(nlgn) solution works in this way:-

First sort the array using merge sort or quick sort(for inplace). Find if sum - array_element is there in this sorted array. One can use binary search for that.

So total time complexity: O(nlgn) + O(lgn) -> O(nlgn).

Answer 6

Ruby implementation

ar1 = [ 32, 44, 68, 54, 65, 43, 68, 46, 68, 56]
for i in 0..ar1.length-1
 t  = 100 - ar1[i]
  if ar1.include?(t)
    s= ar1.count(t)
    if s < 2
      print   s , " - " ,  t, " , " , ar1[i]  , " pair ", i, "\n"
    end
  end
end