CODEWITHSUNDEEP
javascript
Devmix
Devmix

Reputation: 1848

Better way to find two array elements that add up to a given number

I wrote this code that works just fine. However I think there may be a cleaner/better way of doing this. Basically I have to create a function that takes 2 arguments (array and sum), and return the 2 elements that when adding them together is equals the sum parameter. Does anyone know how to refactor this code or make it simpler?

Here's my code:

var list = [2, 6, 20, 4, 11, 30, 5];
var sum = 9;
var myArray = [];

function findTwoNumbers(arr, sum) {
  for (var i = 0; i < arr.length; i++) {
    for (var j = i + 1; j < arr.length; j++) {
      if (arr[i] + arr[j] === sum) {
        myArray.push(arr[i], arr[j]);
      }
    }
  }

  return myArray;
}

console.log(findTwoNumbers(list, sum)); // [4 , 5]

Upvotes: 0

Views: 739

Answers (6)

Mitya
Mitya

Reputation: 34556

The obvious problem with your code currently as it will return an array of multiple pairs if there is more than one combination to achieve the sum from the input numbers. So for example:

let list = [1, 2, 4, 1];
let sum = 5;
//would give [1, 4, 4, 1];

Assuming you want just the first pair, there's no reason to maintain an array (and certainly not one outside the function) - just return immediately:

function findTwoNumbers(arr, sum) {
    for (let i = 0; i < arr.length; i++)
        for (let j = i + 1; j < arr.length; j++)
            if (arr[i] + arr[j] === sum)
                return [arr[i], arr[j]];
}

There are further efficiencies and simplicities we can make. Firstly, the loop should ignore any number which is, in itself, higher than sum-1 (since this is the highest a number can be to still achieve the sum with the help of another number, which have to be 1.)

And since it's midnight, how about some pointless syntax sugar?

function findTwoNumbers(arr, sum) {
    let nums = arr.filter(num => num < sum);
    return nums.map(num => {
        return nums.filter(num2 => num + num2 == sum)[0];
    }).filter(x => x);
}

Upvotes: 0

Brad
Brad

Reputation: 8668

How about this:

Basically take the sum and subtract the first number in the array to get the remainder, then check if the remainder exists in the array, if not move on to the next.

let list = [2, 6, 20, 4, 11, 30, 5];
let sum = 9;

function findTwoNumbers(list, sum) {
  for (let i = 0; i < list.length; i++) {
  	let n =list[i];
    if (list.includes(sum - n)) {
      return [sum - n, n];
    }
  }
}

console.log(findTwoNumbers(list, sum))

Upvotes: 0

Amadan
Amadan

Reputation: 198314

Your code is O(N^2). You can reduce it a bit by using a set (though it has a startup cost of constructing the set, so you probably get raw speedup only for large arrays):

function findTwoNumbers(arr, sum) {
  const arrset = new Set(arr);
  const answer = arr.find(e => e + e !== sum && arrset.has(sum - e));
  return answer === undefined ? null : [answer, sum - answer];
}

Upvotes: 3

Barmar
Barmar

Reputation: 780724

Turn the array into a Set. Then iterate through the array and test whether sum - element is in the set.

I need to check for diff == element to prevent returning a match from adding an element to itself.

var list = [2, 6, 20, 4, 11, 30, 5];
var sum = 9;

function findTwoNumbers(arr, sum) {
  const set = new Set(arr);
  for (let i = 0; i < arr.length; i++) {
    let element = arr[i];
    let diff = sum - element;
    if (diff != element && set.has(diff)) {
      return [element, diff];
    }
  }
}

console.log(findTwoNumbers(list, sum)); // [4 , 5]
console.log(findTwoNumbers([2, 5], 4)); // undefined

Upvotes: 2

Mark Pichler
Mark Pichler

Reputation: 26

Another way would be to first sort the array (O(nlog(n)) then traverse the array and for each element, find the difference between (sum - element) and then do a binary search (O(log(n)) for that value.

For example, the first element is 2, so you would binary search the sorted array for 7 (9 - 2 = 7) and if you find it, then 2 and 7 are a pair. You can stop short too as soon as you reach an element that is greater than (sum/2).

Hope this helps.

Upvotes: 0

Orel Eraki
Orel Eraki

Reputation: 12196

You can return an array without the need of external array

function findTwoNumbers(arr, sum){
    for (var i = 0; i < arr.length; i++) {
        for(var j = i + 1; j < arr.length; j++){
            if(arr[i] + arr[j] === sum){
                return [arr[i] , arr[j]];
            }
        }
    }

    return [];
}

Note: This will only search for the first pair that satisfy the condition, there could be more pairs down the iteration path.

Upvotes: 0

Related Questions