pair-finder.js

// GIST to find pairs of numbers within an array that is greater than the sum of all numbers in the array

// first GOTCHA, make sure you don't multiply a number by itself
// second GOTCHA, make sure numbers aren't multiplied in reverse! (eg 10 * 8 and 8 * 10)

function bruteForce() {

  // unsorted list
  var list = [ 3, 10, 4, 9, 8, 7 ];
  // sum of all numbersin list
  var limit = 41;
  var pairs = [];
  var count = 0;
  
  // nested for loops to compare each number against every other number
  // this is not efficient, because we're making extra comparisons
  for (var firstDigit = 0; firstDigit < list.length; firstDigit++) {
    // the second digital has to begin at the number AFTER the first digit
    // if we make it begin at the beginning of the array, we will double the number of answers
    // if we make it the same, it'll just skip the first comparison anyway
    for (var secondDigit = firstDigit + 1; secondDigit < list.length; secondDigit++) {
      count++; // for counting iterations
      if (firstDigit !== secondDigit) { // if they're not equal (no 10 * 10)
        result = list[firstDigit] * list[secondDigit];
      }
      if (result > limit) {
        pairs.push([list[firstDigit], list[secondDigit]]) // make an array of arrays
      }
    }
  }
  console.log(`Brute Forced answers in ${count} iterations:\n`, pairs);
}


// BONUS ANSWER FOR ASCENDING SORTED LISTS
function efficient() {
  var list = [ 3, 4, 7, 8, 9, 10,];
  // sum of all numbersin list
  var limit = 41;
  var pairs = [];
  var count = 0;

  for (var firstDigit = list.length - 1; firstDigit != -1; firstDigit--) {
    for (var secondDigit = firstDigit - 1; secondDigit != -1; secondDigit--) {
      count++;
      // if we descend down the list, once 10 * 4 is below the limit, we don't need to go down any further, since we know that 10 * 3 won't be above either
      result = list[firstDigit] * list[secondDigit];
      if (result > limit) {
        pairs.push([list[firstDigit], list[secondDigit]])
      } else {
        break;
      }
    }
  }
  console.log(`Efficient answers in ${count} iterations:\n`, pairs);
}


bruteForce();
// efficient();