CODEWITHSUNDEEP
java
youngdev
youngdev

Reputation: 617

Find complementary pairs in array in Java

I am attempting to find how many pairs of values in a given array of integers sum to a specified value k. The logic works if the list contains duplicate values, provided each value has only one complement in the list to sum to k. The issue is that if multiple complements to a given value exist in the list, only one match is counted.

What I have attempted so far is as follows:

  int numberOfWays(int[] arr, int k) {
    // Write your code here
    int output = 0;
    HashMap<Integer, Integer> map = new HashMap();
    for(int i = 0; i < arr.length; i++) {
      int complement = k - arr[i];
      if(map.containsKey(complement)) {
        output++;
      }
      map.put(arr[i],i);
      System.out.println(map);
    }
    return output;
  }

This works for a case as such: k = 6, arr = [1, 2, 3, 4, 3] However, it doesn't work when there are more than two duplicates: k = 6, arr = [1, 5, 3, 3, 3]

For the case that doesn't work the expected result is 4 but the actual is 3.

I can't seem to figure out why that's the case. Any ideas?

Upvotes: 1

Views: 1255

Answers (2)

PatrickChen
PatrickChen

Reputation: 1430

The reason it didn't work for the second one is, 3 should match 2 other 3s. But map only supports one. The change should be:


 int numberOfWays(int[] arr, int k) {
    // Write your code here
    int output = 0;
    HashMap<Integer, Integer> map = new HashMap();
    for(int i = 0; i < arr.length; i++) {
      int complement = k - arr[i];
      int count = map.getOrDefault(arr[i], 0);
      if(map.containsKey(complement)) {
        count = map.get(complement);
        output = output + count; // 2 3s, should match twice.
      }
      map.put(arr[i], count + 1);
      System.out.println(map);
    }
    return output;
  }

Upvotes: 4

WJS
WJS

Reputation: 40057

Another solution. It works on three principles.

  • do a frequency count of the supplied array.
  • for values of k that are even, and arr[i] == k/2 the count is (v(v-1)/2 where v
    is the value for that key. So if k = 8 and the array contains four 4's, then the count, v would be 4 and the sum combinations would be 6.
  • for values that don't meet the above, the count is the product of the two summands freqencies. So if k = 8 and there are three 3's and two 5's the combinations would be three x two == 6.
  • the total count is the sum of all the above computations for each pair of summands that add to k
static int numberOfWays(int[] arr, int k) {
    int count = 0;
    Map<Integer, Integer> map = new HashMap<>();
    // accumulate a frequency count values
    for (int i = 0; i < arr.length; i++) {
        map.compute(arr[i], (key, val) -> val == null ? 1 : val + 1);
    }
    System.out.println(map);
    // copy keys to list for iteration to avoid
    // concurrent mod exception when removing keys from
    // map.  This works better than using an iterator.
    List<Integer> keys = new ArrayList<>(map.keySet());
    for (int key : keys) {
        if ((k&1) == 0 && map.containsKey(key) &&  key == k/2) {
            int v = map.get(key) - 1;
            count = count + ((v * (v + 1)) / 2);
        } else if (map.containsKey(k-key)) {
            System.out.println("trying");
            count += (map.get(key) * map.get(k - key));
        }

        map.remove(key);
    }
    return count;
}

Upvotes: 0

Related Questions