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?
If you have a sorted array you can find such a pair in O(n) by moving two pointers toward the middle
i = 0
j = n-1
while(i < j){
if (a[i] + a[j] == target) return (i, j);
else if (a[i] + a[j] < target) i += 1;
else if (a[i] + a[j] > target) j -= 1;
}
return NOT_FOUND;
The sorting can be made O(N) if you have a bound on the size of the numbers (or if the the array is already sorted in the first place). Even then, a log n factor is really small and I don't want to bother to shave it off.
proof:
If there is a solution (i*, j*), suppose, without loss of generality, that i reaches i* before j reaches j*. Since for all j' between j* and j we know that a[j'] > a[j*] we can extrapolate that a[i] + a[j'] > a[i*] + a[j*] = target and, therefore, that all the following steps of the algorithm will cause j to decrease until it reaches j* (or an equal value) without giving i a chance to advance forward and "miss" the solution.
The interpretation in the other direction is similar.
An O(N) time and O(1) space solution that works on a sorted array:
Let M be the value you're after. Use two pointers, X and Y. Start X=0 at the beginning and Y=N-1 at the end. Compute the sum sum = array[X] + array[Y]. If sum > M, then decrement Y, otherwise increment X. If the pointers cross, then no solution exists.
You can sort in place to get this for a general array, but I'm not certain there is an O(N) time and O(1) space solution in general.
My solution in Java (Time Complexity O(n)), this will output all the pairs with a given sum
import java.util.HashMap;
import java.util.Map;
public class Test {
public static void main(String[] args) {
// TODO Auto-generated method stub
Map<Integer, Integer> hash = new HashMap<>();
int arr[] = {1,4,2,6,3,8,2,9};
int sum = 5;
for (int i = 0; i < arr.length; i++) {
hash.put(arr[i],i);
}
for (int i = 0; i < arr.length; i++) {
if(hash.containsKey(sum-arr[i])){
//System.out.println(i+ " " + hash.get(sum-arr[i]));
System.out.println(arr[i]+ " " + (sum-arr[i]));
}
}
}
}
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).
AS @PengOne mentioned it's not possible in general scheme of things. But if you make some restrictions on i/p data.
Step 1: Move all elements less than SUM to the beginning of array, say in N Passes we have divided array into [0,K] & [K, N-1] such that [0,K] contains elements <= SUM.
Step 2: Since we know bounds (0 to SUM) we can use radix sort.
Step 3: Use binary search on A[K], one good thing is that if we need to find complementary element we need only look half of array A[K]. so in A[k] we iterate over A[ 0 to K/2 + 1] we need to do binary search in A[i to K].
So total appx. time is, N + K + K/2 lg (K) where K is number of elements btw 0 to Sum in i/p A[N]
Note: if you use @PengOne's approach you can do step3 in K. So total time would be N+2K which is definitely O(N)
We do not use any additional memory but destroy the i/p array which is also not bad since it didn't had any ordering to begin with.
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
Here's an O(N) algorithm. It relies on an in-place O(N) duplicate removal algorithm, and the existence of a good hash function for the ints in your array.
First, remove all duplicates from the array.
Second, go through the array, and replace each number x with min(x, S-x) where S is the sum you want to reach.
Third, find if there's any duplicates in the array: if 'x' is duplicated, then 'x' and 'S-x' must have occurred in the original array, and you've found your pair.
take two pointers one starts from 0th index of array, and another from end of array say (n-1).
run the loop until low <= high
Sum = arr[low] + arr[high]
if(sum == target)
print low, high
if(sum < target)
low++
if(sum > target)
high--
Step 2 to 10 takes O(n) time, and counting sort takes O(n). So total time complexity will be O(n).
In javascript : This code when n is greater then the time and number of iterations increase. Number of test done by the program will be equal to ((n*(n/2)+n/2) where n is the number of elements.The given sum number is discarded in if (arr[i] + arr[j] === 0) where 0 could be any number given.
var arr = [-4, -3, 3, 4];
var lengtharr = arr.length;
var i = 0;
var j = 1;
var k = 1;
do {
do {
if (arr[i] + arr[j] === 0) { document.write(' Elements arr [' + i + '] [' + j + '] sum 0'); } else { document.write('____'); }
j++;
} while (j < lengtharr);
k++;
j = k;
i++;
} while (i < (lengtharr-1));
First off, sort the array using radix sort. That'll set you back O(kN). Then proceed as @PengOne suggest.
Here is a solution witch takes into account duplicate entries. It is written in javascript and runs using sorted and unsorted arrays. The solution runs in O(n) time.
var count_pairs_unsorted = function(_arr,x) {
// setup variables
var asc_arr = [];
var len = _arr.length;
if(!x) x = 0;
var pairs = 0;
var i = -1;
var k = len-1;
if(len<2) return pairs;
// tally all the like numbers into buckets
while(i<k) {
asc_arr[_arr[i]]=-(~(asc_arr[_arr[i]]));
asc_arr[_arr[k]]=-(~(asc_arr[_arr[k]]));
i++;
k--;
}
// odd amount of elements
if(i==k) {
asc_arr[_arr[k]]=-(~(asc_arr[_arr[k]]));
k--;
}
// count all the pairs reducing tallies as you go
while(i<len||k>-1){
var y;
if(i<len){
y = x-_arr[i];
if(asc_arr[y]!=undefined&&(asc_arr[y]+asc_arr[_arr[i]])>1) {
if(_arr[i]==y) {
var comb = 1;
while(--asc_arr[_arr[i]] > 0) {pairs+=(comb++);}
} else pairs+=asc_arr[_arr[i]]*asc_arr[y];
asc_arr[y] = 0;
asc_arr[_arr[i]] = 0;
}
}
if(k>-1) {
y = x-_arr[k];
if(asc_arr[y]!=undefined&&(asc_arr[y]+asc_arr[_arr[k]])>1) {
if(_arr[k]==y) {
var comb = 1;
while(--asc_arr[_arr[k]] > 0) {pairs+=(comb++);}
} else pairs+=asc_arr[_arr[k]]*asc_arr[y];
asc_arr[y] = 0;
asc_arr[_arr[k]] = 0;
}
}
i++;
k--;
}
return pairs;
}
Start at both side of the array and slowly work your way inwards keeping a count of how many times each number is found. Once you reach the midpoint all numbers are tallied and you can now progress both pointers counting the pairs as you go.
It only counts pairs but can be reworked to
Enjoy!
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
Here is a solution in python:
a = [9, 8, 9, 2, 15, 11, 21, 8, 9, 2, 2, 8, 9, 2, 15, 11, 21, 8, 9, 2, 9, 8, 9, 2, 15, 11, 21, 8, 9, 2, 2, 8, 9, 2, 15, 11, 2, 8, 9, 2, 2, 8,
9, 2, 15, 11, 21, 8, 9, 12, 2, 8, 9, 2, 15, 11, 21, 7, 9, 2, 23, 8, 9, 2, 15, 11, 21, 8, 9, 2, 2, 12, 9, 2, 15, 11, 21, 8, 9, 2, 2,
8, 9, 2, 15, 11, 21, 8, 9, 2, 2, 8, 9, 2, 15, 11, 21, 8, 9, 2, 2, 8, 9, 2, 15, 11, 21, 8, 9, 2, 2, 7.12, 9, 2, 15, 11, 21, 8, 9, 2, 2, 8, 9,
2, 15, 11, 21, 8, 9, 2, 2, 8, 9, 2, 15, 11, 21, 8, 9, 2, 2, 8, 9, 2, 15, 11, 21, 8, 9, 2, 2, 8, 9, 2, 15, 11, 21, 8, 0.87, 78]
i = 0
j = len(a) - 1
my_sum = 8
finded_numbers = ()
iterations = 0
while(OK):
iterations += 1
if (i < j):
i += 1
if (i == j):
if (i == 0):
OK = False
break
i = 0
j -= 1
if (a[i] + a[j] == my_sum):
finded_numbers = (a[i], a[j])
OK = False
print finded_numbers
print iterations
I was asked this same question during an interview, and this is the scheme I had in mind. There's an improvement left to do, to permit negative numbers, but it would only be necessary to modify the indexes. Space-wise ain't good, but I believe running time here would be O(N)+O(N)+O(subset of N) -> O(N). I may be wrong.
void find_sum(int *array_numbers, int x){
int i, freq, n_numbers;
int array_freq[x+1]= {0}; // x + 1 as there could be 0’s as well
if(array_numbers)
{
n_numbers = (int) sizeof(array_numbers);
for(i=0; i<n_numbers;i++){ array_freq[array_numbers[i]]++; } //O(N)
for(i=0; i<n_numbers;i++)
{ //O(N)
if ((array_freq[x-array_numbers[i]] > 0)&&(array_freq[array_numbers[i]] > 0)&&(array_numbers[i]!=(x/2)))
{
freq = array_freq[x-array_numbers[i]] * array_freq[array_numbers[i]];
printf(“-{%d,%d} %d times\n”,array_numbers[i],x-array_numbers[i],freq );
// “-{3, 7} 6 times” if there’s 3 ‘7’s and 2 ‘3’s
array_freq[array_numbers[i]]=0;
array_freq[x-array_numbers[i]]=0; // doing this we don’t get them repeated
}
} // end loop
if ((x%2)=0)
{
freq = array_freq[x/2];
n_numbers=0;
for(i=1; i<freq;i++)
{ //O([size-k subset])
n_numbers+= (freq-i);
}
printf(“-{%d,%d} %d times\n”,x/2,x/2,n_numbers);
}
return;
}else{
return; // Incoming NULL array
printf(“nothing to do here, bad pointer\n”);
}
}
Critics are welcomed.
In java, this is depends on max number in array. it returns an int[] having the indexes of two elements. it is O(N).
public static int[] twoSum(final int[] nums, int target) {
int[] r = new int[2];
r[0] = -1;
r[1] = -1;
int[] vIndex = new int[0Xffff];
for (int i = 0; i < nums.length; i++) {
int delta = 0Xfff;
int gapIndex = target - nums[i] + delta;
if (vIndex[gapIndex] != 0) {
r[0] = vIndex[gapIndex];
r[1] = i + 1;
return r;
} else {
vIndex[nums[i] + delta] = i + 1;
}
}
return r;
}
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);
Naïve double loop printout with O(n x n) performance can be improved to linear O(n) performance using O(n) memory for Hash Table as follows:
void TwoIntegersSum(int[] given, int sum)
{
Hashtable ht = new Hashtable();
for (int i = 0; i < given.Length; i++)
if (ht.Contains(sum - given[i]))
Console.WriteLine("{0} + {1}", given[i], sum - given[i]);
else
ht.Add(given[i], sum - given[i]);
Console.Read();
}
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
//C# - https://dotnetfiddle.net/6fMtze
private static void PairNumbers(int[] numbers, int? _min, int sum)
{
if (numbers.Count() <= 1) return;
int min = numbers[0];
int max = numbers[^1];
if (_min == max) return;
var numberList = numbers.ToList();
if (min + max >= sum)
{
if (min != _min)
{
Console.WriteLine("{" + min + ", " + max + "}");
}
numberList.RemoveAt(numberList.Count - 1);
RemoveDuplicates(numberList, min, max);
}
else
{
numberList.RemoveAt(0);
}
PairNumbers(numberList.ToArray(), min, sum);
}
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
??
