Find the two numbers that will equal the desired sum

Question

I had a technical interview and one of the questions was to find the two numbers in the array that would equal the desired sum. For the life of me, I can not find the solution.

var input = [3, 5, 7, 9, 4, 8, 5, 12, 4, 9, 16, 5];
var dSum = 28; // return would be [12,16]

Answer 1

Use a Set(), for solving this problem in O(n). The approach is simple :

• Take an empty set. And for each element e in input check:

  (a) If the set contains sum - e . if yes then print the pair (e, sum -e) .

  (b) Insert e into set.

  Try the following:

let input = [3, 5, 7, 9, 4, 8, 5, 12, 4, 9, 16, 5];
let dSum = 28;
let set = new Set();

for(item of input) {
  let num = dSum - item;
  if(set.has(num)) {
    console.log(num + " " + item);
    break;
  }
  set.add(item);
}

Answer 2

Please have a look at this simple code because I'm pretty sure this is what you need:

function detectPair(sum, array) {
  for (i=0; i<array.length; i++) {
    for (j=0; j<array.length; j++) {
      if (i == j) continue;
      else if (array[i] + array[j] === sum) return [array[i], array[j]];
    }
  }; return null;
}


let sum = 28;
let array = [3, 5, 7, 9, 4, 8, 5, 12, 4, 9, 16, 5]

console.log(detectPair(sum, array)); //return would be [12,16]

---

Edit @uom-pgregorio: 'There wasn't any constraints that the same number can't be used. So a 14 + 14 in this case should still be accepted'

I'm pretty sure you've mixed something up: The line if (i == j) continue; is not preventing the situation that 14+14 is correct, it is preventing that if the array just includes a number (like 14) it uses the same number a several times.

==> `i == j` is checking the indexes not the values

Maybe just try this setup:

let sum = 28;
let array = [3, 5, 7, 14, 14] // includes 14 two times

Answer 3

function findSumPair(input, target) {
   for(let a = 0; a < input.length; a++) {
      for(let b = a; b < input.length; b++) {
         if(input[a]+input[b] === target)
            return [input[a], input[b]];
      }
   }
}
console.log(findSumPair([3, 5, 7, 9, 4, 8, 5, 12, 4, 9, 16, 5], 28));

The inner loop can be started at the current index of the outer loop (rather than 0) because the previous combinations have already been checked.

Answer 4

var input = [3, 5, 7, 9, 4, 8, 5, 12, 4, 9, 16, 5];
var dSum = 28; // return would be [12,16]

let el1 = Math.max(...input)
let el2 = Math.max(...input.filter(i => i !== el1))

console.log([el1, el2])

Or

let input = [3, 5, 7, 9, 4, 8, 5, 12, 4, 9, 16, 5];
let dSum = 28; // return would be [12,16]
let result

for (let i = 0; i < input.length; i++)
  for (let k = i; k < input.length; k++)
    if (i !== k && input[i] + input[k] === dSum)
      result = [input[i], input[k]]

console.log(result)

Answer 5

Beside the double nested solutions and solutions with more than one loop, you could use a single loop approach with a hash table for the still missing number and a short circuit if this number is found in the array.

This approach is a fast one, because it uses a for loop with an object as storage for a fast access, and a variable value for array[i].

Big O is in worst case O(n).

function getPair(array, sum) {
    var i, l,
        hash = Object.create(null),
        value;
        
    for (i = 0, l = array.length; i < l; i++) {
        value = array[i];
        if (hash[value]) {
            return [sum - value, value];
        }
        hash[sum - value] = true;
    }
}

console.log(getPair([3, 5, 7, 9, 4, 8, 5, 12, 4, 9, 16, 5], 28));

Answer 6

I'd say this works, but the algorithm is really bad, O(n^2) I think.

for (i of input) {
    for (j of input) {
        if (i + j == dSum)
            console.log([i, j]);
    }
}

Answer 7

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

console.log(findPair([3, 5, 7, 9, 4, 8, 5, 12, 4, 9, 16, 5], 28));

Answer 8

Try the following:

   for (var i = 0; i < input.length; i++)
    for (var j = 0; J < input.length; j++)
        if (input[i]+input[j] == dSum)
            console.log([input[i], input[j]])

Edit: I thought there was a constraint of i<>j. I removed that constraint

Answer 9

var input = [3, 5, 7, 9, 4, 8, 5, 12, 4, 9, 16, 5];
var dSum = 28;
twoSum(input, dSum);
function twoSum (arr, target) {
  let results = [];
  for (let i=0; i<arr.length; i++) {
    for (let j=i+1; j<arr.length; j++) {
      if (arr[j] === target - arr[i]) {
        results.push([arr[i], arr[j]])
      }
    }
  }
  return results;
}

Answer 10

@amrender-singh Has the best answer here.

To honour him, here's a snippet using his code to find the first or all sums with a certain value in an Array

const log = (...strs) => 
  document.querySelector("pre").textContent += `${strs.join(" ")}\n`;
const array = [3, 5, 7, 9, 4, 8, 5, 12, 4, 9, 16, 5];

log("All possible sums 28 in array:", findSumsInArray(array, 28));
log("First sum 28 in array:", findSumsInArray(array, 28, true));
log("All possible sums 22 in array:", findSumsInArray(array, 22));
log("First sum 22 in array:", findSumsInArray(array, 22, true));
log("All possible sums 12 in array:", findSumsInArray(array, 12));
log("First sum 12 in array:", findSumsInArray(array, 12, true));
log("First sum 28 in array [3, 5, 7, 14, 14]:", 
     findSumsInArray([3, 5, 7, 14, 14], 28, true));

function findSumsInArray(array, sum2Find, firstOnly) {
  let set = new Set(array);
  let result = [];
  const errorStr = `Sum ${sum2Find} not possible in [${array}]`;
  for (let item of array) {
    let num = sum2Find - item;
    if (set.has(num)) {
      const report = `${num}+${item}`;
      if (firstOnly) {
        return report;
      }
      result.push(report);
      set.delete(item);
   }
  }
  return result.length ? `[${result.join(", ")}]` : errorStr;
}

<pre></pre>

Answer 11

I'm a bit late in contributing, but no one appears to have posted the obligatory JavaScript one-liner.

let input = [3, 5, 7, 9, 4, 8, 5, 12, 4, 9, 16, 5];
let dSum = 28;
let Result = [];

input.forEach( i=>{ input.forEach( j=>{ i+j==dSum && Result.push([i,j]); }); });

The Result array will contain the solutions, of which there are two in this case:

[[12, 16], [16, 12]]

Generalising this to a function where values representing input and dSum are user-defined parameters:

pairsFromArrayWithSum = (total, Numbers) 
                      => Numbers.forEach(a => { 
                         Numbers.forEach(b => { 
                         a + b == total && Result.push([a,b]);
                         }); });

Then, given:

Result = [];
pairsFromArrayWithSum(50, [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]);

the Result array will contain:

[ [ 3, 47 ],
  [ 7, 43 ],
  [ 13, 37 ],
  [ 19, 31 ],
  [ 31, 19 ],
  [ 37, 13 ],
  [ 43, 7 ],
  [ 47, 3 ] ]

Answer 12

let input = [3, 5, 7, 9, 4, 8, 5, 12, 4, 9, 16, 5];
let dSum = 28;
let set = new Set();

for(item of input) {
  let num = dSum - item;
  if(set.has(num)) {
    console.log(num + " " + item);
    break;
  }
  set.add(item);
}

function detectPair(sum, array) {
  for (i=0; i<array.length; i++) {
    for (j=0; j<array.length; j++) {
      if (i == j) continue;
      else if (array[i] + array[j] === sum) return [array[i], array[j]];
    }
  }; return null;
}


let sum = 28;
let array = [3, 5, 7, 9, 4, 8, 5, 12, 4, 9, 16, 5]

console.log(detectPair(sum, array)); //return would be [12,16]

function detectPair(sum, array) {
  for (i=0; i<array.length; i++) {
    for (j=0; j<array.length; j++) {
      if (i == j) continue;
      else if (array[i] + array[j] === sum) return [array[i], array[j]];
    }
  }; return null;
}


let sum = 28;
let array = [3, 5, 7, 9, 4, 8, 5, 12, 4, 9, 16, 5]

console.log(detectPair(sum, array)); //return would be [12,16]