Find all unique pairs of element in an array that sum to S. For ex. If array = {2,4,6,4,6} and S = 8 then answer is {(2,6), (4,4)}
// take the array.
$elements = array(1,2,3,4,6,4, 1);
$sum = 2;
sort($elements);
// now that it took nlogn, we should do away with O(n) next.
$left = 0;
$right = count($elements)- 1;
echo "left value=".$left." right value=".$right;
// goto the sum value. one value lesser than sum actually
for ( $i = $right; $elements[$i] > $sum; $i--)
{}
// final logic. now loop thru
// left should never be greater than right.
// if sum-right is greater than left -> increment left
// if sum-right is less than left -> stop there. this element has no pair. and decrement right.
for( ; $left < $right; )
{
if( ($sum - $elements[$right]) > $elements[$left])
{
// increment left
$left++;
}
else if( ($sum - $elements[$right]) < $elements[$left] )
{
// decrement right. no pair found
$right--;
}
else
{
// equals output a pair. and decrement right.
echo "Pair: (".$elements[$left].",".$elements[$right].")";
// now decrement right until duplicates are all skipped.
for( $dec = $elements[$right];
$dec == $elements[$right];
$right--){}
}
}
The solution is O(n logn) .. can we do better ?
//java code: O(nlogn)
ReplyDeleteimport java.util.Arrays;
public class uniquePairs {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.print("input");
//int input[] = {1,2,3,5,6,4,1};
int input[] = {1,1,1,1,1,6,6,6,6,-6,-7,-8};
int sum = 7;
Arrays.sort(input);
int j = input.length -1;
for(int i=0; i< input.length; i++)
{
int x = input[i];
if(i < input.length-1 && input[i] == input[i+1]){
continue;
}
int y = sum - x;
if (y <= 0){
continue;
}
if(i < j){
for(int k=j; i < k ; k--){
if(input[k] == y)
{
System.out.println("{" + x+ "," + y+"}");
j = k -1;
break;
}
}
}
}
}
}
We can do it in O(n) if we use some space. The approach is simple - since we know we have to find x and y such that x+y=n, Hash all elements of the array and search for y (which is n-x) in the hashed array. Each collision means we have found a pair with required properties.
ReplyDeleteSummary:
- Hash the array a[] on to h[].
- For each element in a[]
- search for n-a[i] in h[] (by hashing it and detecting a collision)
- if there is a collision print pair (i, [index of the collided element])
This doesn't work for cases where there's only one element x and when n-x = y = x.
DeleteIt should also take care of -ve numbers, duplicates and collisions in the hashing technique itself.
Non negative , non duplicate and non collision hashing technique , that doesn't work for n-x=x solution. I already have this.
ReplyDelete<?php
$elements = array(1,2,4,3,6,4);
$sum = 6;
// parallel array
$parallel = array();
// TODO check for least -ve value and offset all elements with that -ve number.
for ( $i = 0; $i < count($elements); $i++ )
{
$value = $sum-$elements[$i];
$parallel[$value] = $i;
echo " par[".$value."]= ".$i;
}
// now the parallel is ready. now check for zeroes
for ( $j = 0; $j < count($elements); $j++ )
{
if( array_key_exists( $elements[$j], $parallel ) )
{
echo "(".$elements[$j].",".$elements[$parallel[$elements[$j]]].")";
}
}