Daily Coding Challenge 1

Given an array of numbers, return whether any two sums to K. For example, given [10, 15, 3, 7] and K of 17, return true since 10 + 7 is 17.

Solution 1

const arr = [10, 15, 3, 7]
const target = 17;

function sums(arr, val) {
  let out = false;

  arr.forEach((x, i) => {
    arr.slice(i+1).forEach((y, j) => {
      if (x + y === target) {
        out = true;
      }
    })
  });
  return out;
}

console.log(sums(arr, target));

Runtime: O(n^2)

Proof of correctness

Program terminates because both loops have clearly defined ending points (length of the array).

output is initialized to false.

Every pair of integers in the array is tested.

out can only be set to true if the currently tested pair sums to k.

out can not be set back to false once it is set to true.