Given a list of n integers arr[0..(n-1)], determine the number of different pairs of elements within it which sum to k

Question

I'm tackling this problem and I can't seem to arrive at the correct solution. The question is:

"Given a list of n integers arr[0..(n-1)], determine the number of different pairs of elements within it which sum to k. If an integer appears in the list multiple times, each copy is considered to be different; that is, two pairs are considered different if one pair includes at least one array index which the other doesn't, even if they include the same values.

My approach is that I'm building a map that contains each number in the array and the number of times it occurs. Then I iterate over the map to find my answer.

function numberOfWays(arr, k) {
  let output = 0;
  let map = {};

  // put values and # of occurences into map
  for(let i = 0; i < arr.length; i++) {
    let key = arr[i];
    if(!(key in map)) {
      map[key] = 1;
    } else {
      map[key]++;
    }
  }
  
  for(let key in map) {
    let difference = k-key
    if((difference) in map) {
      if(k/2 === key) {
        output += map[key]*(map[key]-1)/2;
      } else {
        output += map[key] * map[key] / 2;  // divide by 2 so that pairs aren't counted twice
      }
    }
  }

  return output;
}

The two test cases are:

var arr_1 = [1, 2, 3, 4, 3]; expected result: [2] -- I'm getting [3]

var arr_2 = [1, 5, 3, 3, 3]; expected result: [4] -- I'm getting [5.5]

I'm definitely doing something wrong in my calculations, but I can't seem to wrap my ahead around it.

Answer 1

This is one way to nest the loops to find the pairs in array "arr" with the sum "k".

function numberOfWays(arr, k) {
  let output = 0;

  for (i = 0; i < arr.length; i++) {
    for (n = i+1; n < arr.length; n++) {
    if (arr[i] + arr[n] == k)
        output++;
    }
  }
  return output;
}

Answer 2

You could count the smaller and greater values for building k and then taker either the product or if only two of the same value is building the sum take factorial of the cound divided by two.

function numberOfWays(array, k) {
    const
        f = n => +!n || n * f(n - 1),
        pairs = {};

    for (const value of array) {
        const smaller = Math.min(value, k - value);
        pairs[smaller] ??= { one: 2 * smaller === k, min: 0, max: 0 };
        pairs[smaller][value === smaller ? 'min' : 'max']++;
    }

    let count = 0;

    for (const k in pairs) {
        const { one, min, max } = pairs[k];
        if (one) {
            if (min > 1) count += f(min) / 2;
        } else if (min && max) {
            count += min * max;
        }
    }
  
    return count;
}
console.log(numberOfWays([1, 2, 3, 4, 3], 6)); // 2
console.log(numberOfWays([1, 5, 3, 3, 3], 6)); // 4

Answer 3

function numberOfWays(items, k) {
  // Clone as to not mutate original array
  const arr = [...items]
  let count = 0

  // Stop comparing when no items left to compare
  while (arr.length) {
    for (let i = 0; i < arr.length; i++) {
      // Compare each item to the first item
      const sum = arr[0] + arr[i + 1]

      if (sum === k) {
        count++
      }
    }

    // Remove the first item after comparing to the others
    arr.shift()
  }

  return count
}

console.log(numberOfWays([1, 2, 3, 4, 3], 6))
console.log(numberOfWays([1, 5, 3, 3, 3], 6))
console.log(numberOfWays([1, 1, 1, 1, 1], 2))

Answer 4

import math
from math import factorial as f

def get_number_of_combination(n,r):
   return f(n)//(f(n-r)*f(r))


def numberOfWays(arr, k):
  num_count = {}
  num_ways = 0

for i in arr:
  old_count = num_count.get(i,0)
  num_count.update({i: old_count+1})

for i in list(num_count.keys()):
  if i == k - i and num_count.get(i,0) > 1:
    num_ways += (get_number_of_combination(num_count.get(i,0),2))
    num_count.update({i:0})
  else:
    i_n = num_count.get(i, 0)
    ki_n = num_count.get(k-i, 0)
    num_ways += i_n * ki_n
    num_count.update({i:0,k-i:0})
return num_ways