LebGeeks

A community for technology geeks in Lebanon.

You are not logged in.

#26 January 9 2012

xterm
Moderator

Re: [Exercise] Finding the pair

rolf wrote:

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)

Offline

#27 January 14 2012

raja
Member

Re: [Exercise] Finding the pair

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)

Offline

#28 January 14 2012

xterm
Moderator

Re: [Exercise] Finding the pair

raja wrote:

Well, that's not 100% correct xterm, you're supposed to return the number of pairs not the pairs

len(result)

Offline

#29 November 14 2012

Ayman
Member

Re: [Exercise] Finding the pair

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)

Offline

#30 November 26 2012

longbit
Member

Re: [Exercise] Finding the pair

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);
}
}

Offline

#31 January 4 2013

Joe
Member

Re: [Exercise] Finding the pair

A similar question has just been asked on /r/dailyprogrammer. It's worth checking it out for other approaches and new languages.

Offline

#32 November 5 2013

NuclearVision
Member

Re: [Exercise] Finding the pair

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

Offline

#33 November 5 2013

Joe
Member

Re: [Exercise] Finding the pair

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?

Offline

#34 November 5 2013

longbit
Member

Re: [Exercise] Finding the pair

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)

Offline

#35 November 5 2013

NuclearVision
Member

Re: [Exercise] Finding the pair

rahmu wrote:

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)

Offline

Board footer