Find two numbers in array such that they add up to a given a number

The easy way to do this would be a for loop nested inside another.

But I want to solve it this way “check if the array includes both desiredSum-x and x”

let givenArray = [1, 2, 5, 4, 4];
let desiredSum = 7;

// nested for loop

// for (i = 0; i < givenArray.length; i++) {
//   for (j = i + 1; j < givenArray.length; j++) {
//     if (givenArray[i] + givenArray[j] == desiredSum) {
//       flag = 1;
//       console.log(givenArray[i] + " & " + givenArray[j]);
//     }
//   }
// }

// generate all possible sums from desiredSum and check if both of required numbers are available


for (i = 0; i < givenArray; i++) {
    if (givenArray.includes(i) && givenArray.includes(desiredSum-i)) {
        console.log((desiredSum-x) + ' & ' + (x))
    }
}

Answer

The desiredSum - x and x approach is actually done via a cache mechanism. As you iterate over your array, you check for the difference of current element from the desiredSum and if present in cache, add it to the output array. Else you would store the current number in the cache.

Time complexity – O(n)

Space complexity – O(n)

let givenArray = [1, 2, 5, 4, 4,3];
let desiredSum = 7;



function twoSum(desiredSum,givenArray){
let output = [];
let cache = new Set();
for (let i = 0; i < givenArray.length; i++) {
  const firstNumber = givenArray[i];
  const secondNumber = desiredSum - firstNumber;
  if(cache.has(secondNumber)){
   output.push([firstNumber,secondNumber]);
  }
  else{
  cache.add(firstNumber);
  }
}
return output;
}

const result = twoSum(desiredSum,givenArray);

console.log(result);

Leave a Reply

Your email address will not be published. Required fields are marked *