// Input: array of integers, where:
  // The integers are in the range 1..n
  // The array has a length of n+1
// Output: integer that appears more than once, if multiple duplicates, return one of them


// O(n) time, O(n) space:
function findDuplicate(arr) {
    var numbersSeen = new Set();
    for (var i = 0; i < arr.length; i++) {
        var number = arr[i];
        if (numbersSeen.has(number)) {
            return number;
        } else {
            numbersSeen.add(number);
        }
    }
}

// O(n^2) time, O(1) space (nested loop)
function findDuplicate(arr) {
  for (var i = 1; i < arr.length; i++) {
          var hasBeenSeen = false;
          for (var j = 0; j < arr.length; j++) {
              var needle = arr[i];
              var number = arr[j];
              console.log(i, arr[needle], number)
              if (number === needle) {
                  if (hasBeenSeen) {
                      return number;
                  } else {
                      hasBeenSeen = true;
                  }
              }
          }
      }
}