You are not logged in.
I'm not sure I understood the question.
Given an array and a number, find the pairs in the array that sum up to that number.
example 1:
a = [1,2,3,4]
n = 5
Result = (1,4) (2,3)
example 2:
a = [4,5,5,6,7]
n = 10
Result = (4,6) (5,5)
Well, that's not 100% correct xterm, you're supposed to return the number of pairs not the pairs themselves. Also, here's a python 1-liner
from itertools import combinations
def num_pairs(l, s):
"""
Find the number of pairs in l that sum to s
"""
return len(filter(lambda a:sum(a)==s, combinations(l,2)))
And yes, it's cheating because itertools does all the hard work, but it's still a solution :)
PS: http://code.activestate.com/recipes/190465/ has an implementation of combinations(they call it xuniqueCombinations). So if you're stuck on python < 2.6 you can use that instead of itertools.combinations
Last edited by raja (January 14 2012)
Well, that's not 100% correct xterm, you're supposed to return the number of pairs not the pairs
len(result)
Some more grave digging... Just came across this and I don't like at all my naive entry which has a complexity of O(n^2) So here is a simpler and more elegant one. We sort the list of values then we loop through it while keeping two pointers of the left most and right most of the array. On each iteration if the sums of right and left are equal increment left and decrement right, if the sum is greater increment the left only, if it is leff decrement right only.
var set = [1,8,7,5,9,3,2]
var sum = 10;
set.sort();
var left = 0;
var right = set.length-1;
while(left < right)
{
if(set[left]+set[right] == sum)
{
console.log("("+set[left]+","+set[right]+")");
left++;
right--;
}
else if(set[left]+set[right] < sum)
left++;
else
right--;
}
For JavaScript most most ECMAScript engines have different implementations of the sort functions but most of them are similar to merge sort(or better) in terms of complexity that is within O(nlogn). Many other languages have similar or better implementations for the standard sorting function.
So due to sorting the program runs withing O(nlogn) which is of course much better than O(n^2) for large problem size n.
Last edited by Ayman (November 14 2012)
this is a quick answer before i leave to uni, i'll try to enhance it more. (took me about couple of minutes)
public class Pairs {
public static void main(String[] args){
int p1;
int counter=0;
int[] ar = {4,5,5,6,7};
int sum = 10;
for (int i=0; i<ar.length; i++)
{
p1=ar[i];
for(int j = i;j<ar.length-1; j++)
{
if((p1+ar[j])==sum && i!=j){
System.out.println("["+p1+","+ar[j]+"]");
counter++;}
}
}
System.out.println("Number of pairs is: "+counter);
}
}
A similar question has just been asked on /r/dailyprogrammer. It's worth checking it out for other approaches and new languages.
How about this?
print len([[a,b] for a in xrange(1,10) for b in xrange(1,10) if a+b==10 and a>=b]) #x->10
NuclearVision: Can you try to guess which problems your solutions will encounter?
Hint, how will your function behave if you have an array with 1000000 elements?
here's mine...
java
public class FindingPairs {
public static void main(String longbit []){
int ar[] = {1,2,3,5,7,9,3};
int sum = 4;
int count = 0;
for (int i=0 ; i<ar.length ; i++){
for (int j=i ; j<ar.length ; j++){ //replace with int j = i+1 if you don't want the same cell to interpreted as pair
if(ar[i]+ar[j]==sum){
System.out.println("array["+i+"]->"+ar[i] + " + array["+j+"]->"+ar[j]);
count++;
}
}
}
System.out.println("total of "+count+" pair(s) found");
}
}
EDIT: lol now i noticed that i previously did this exercise.
Last edited by longbit (November 5 2013)
NuclearVision: Can you try to guess which problems your solutions will encounter?
Hint, how will your function behave if you have an array with 1000000 elements?
It will go crazy trying to test 1000000**2 combinations.
print len([[a,b] for a in xrange(1,6) for b in xrange(5,10) if a+b==10])
I guess this is my final simplification for it. There s no way around trying at least the right pairs.
Last edited by NuclearVision (November 5 2013)