CODEWITHSUNDEEP
javaalgorithm
Monica Hübner
Monica Hübner

Reputation: 279

Count pairs from an array whose sum is equal to a given number?

I just had an online coding interview and one of the questions asked there is for a given array of integers, find out the number of pairs whose summation is equal to a certain number (passed as parameter inside the method ). For example an array is given as, 

int[] a = {3, 2, 1, 45, 27, 6, 78, 9, 0};
int k = 9; // given number

So, there will be 2 pairs (3, 6) and (9, 0) whose sum is equal to 9. It's good to mention that how the pairs are formed doesn't matter. The means (3,6) and (6,3) will be considered as same pair. I provided the following solution (in Java) and curious to know if I missed any edge cases? 

public static int numberOfPairs(int[] a, int k ){

    int len = a.length;

    if (len == 0){
      return -1;
    }

    Arrays.sort(a);
    int count  = 0, left = 0, right = len -1; 

    while( left < right ){

        if ( a[left] + a[right] == k  ){

            count++; 

            if (a[left] == a[left+1] && left < len-1 ){
              left++;
            }

            if ( a[right] == a[right-1] && right >1 ){
              right-- ; 
            }

            right--; // right-- or left++, otherwise, will get struck in the while loop 
        }

        else if ( a[left] + a[right] < k ){
          left++;
        }

        else {
          right--;
        }
    }

    return count; 
}

Besides, can anyone propose any alternative solution of the problem ? Thanks.

Upvotes: 2

Views: 19458

Answers (5)

viveksuggu
viveksuggu

Reputation: 777

This code will give you count of the pairs that equals to given sum and as well as the pair of elements that equals to sum

 private void pairofArrayElementsEqualstoGivenSum(int sum,Integer[] arr){
        int count=0;
        List numList = Arrays.asList(arr);
        for (int i = 0; i < arr.length; i++) {
            int num = sum - arr[i];
            if (numList.contains(num)) {
                count++;
                System.out.println("" + arr[i] + " " + num + " = "+sum);
            }
        }
        System.out.println("Total count of pairs "+count);
    }

Upvotes: 0

tharindu_DG
tharindu_DG

Reputation: 9261

Following solution will return the number of unique pairs

public static int numberOfPairs(Integer[] array, int sum) {
    Set<Integer> set = new HashSet<>(Arrays.asList(array));

    // this set will keep track of the unique pairs.
    Set<String> uniquePairs = new HashSet<String>();

    for (int i : array) {
        int x = sum - i;
        if (set.contains(x)) {
            int[] y = new int[] { x, i };
            Arrays.sort(y);
            uniquePairs.add(Arrays.toString(y));
        }
    }

    //System.out.println(uniquePairs.size());
    return uniquePairs.size();
}

The time complexity will be O(n).

Hope this helps.

Upvotes: 9

p_flame
p_flame

Reputation: 112

You can use the HashMap<K,V> where K: a[i] and V: k-a[i] This may result in an incorrect answer if there are duplicates in an array.

Say for instances: 

int a[] = {4, 4, 4, 4, 4, 4, 4, 4, 4}

where k = 8 or:

int a[] = {1, 3, 3, 3, 3, 1, 2, 1, 2}

where k = 4.

So in order to avoid that, we can have a List<List<Integer>> , which can check each pair and see if it is already in the list.

static int numberOfPairs(int[] a, int k)
{
    List<List<Integer>> res = new ArrayList<>();
    Map<Integer, Integer> map = new HashMap<>();
    for(int element:a)
    {
        List<Integer> list = new ArrayList<>();
        if(map.containsKey(element))
        {
            list.add(element);
            list.add(map.get(element));
            if(!res.contains(list))
                res.add(list);
        }
        else
            map.put(k - element, element);        
    }
    return res.size();
}

Upvotes: 1

Gunnar Sir&#233;us
Gunnar Sir&#233;us

Reputation: 182

Given an array of integers and a target value, determine the number of pairs of array elements with a difference equal to a target value. The function has the following parameters:

k: an integer, the target difference

arr: an array of integers

Using LINQ this is nice solution:

    public static int CountNumberOfPairsWithDiff(int k, int[] arr)
    {
        var numbers = arr.Select((value) => new { value });
        var pairs = from num1 in numbers
                    join num2 in numbers
                    on num1.value - k equals num2.value
                    select new[]
                {
                    num1.value, // first number in the pair
                    num2.value, // second number in the pair
                };
        foreach (var pair in pairs)
        {
            Console.WriteLine("Pair found: " + pair[0] + ", " + pair[1]);
        }

        return pairs.Count();
    }

Upvotes: -1

Guillaume F.
Guillaume F.

Reputation: 6463

Your solution is overly complex, you can do this exercise in a much easier manner:

public static int numberOfPairs(int[] a, int k ){

    int count=0;
    List<Integer> dedup = new ArrayList<>(new HashSet<>(Arrays.asList(a)));
    for (int x=0 ; x < dedup.size() ; x++ ){
        for (int y=x+1 ; y < dedup.size() ; y++ ){
            if (dedup.get(x)+dedup.get(y) == k)
                count++;
        }
    }

    return count;
}

The trick here is to have a loop starting after the first loop's index to not count the same values twice, and not compare it with your own index. Also, you can deduplicate the array to avoid duplicate pairs, since they don't matter.

You can also sort the list, then break the loop as soon as your sum goes above k, but that's optimization.

Upvotes: 0

Related Questions