Determine if any number from one array added to any number from another array equal a target number

Question

I am having trouble solving below question. I am given 2 arrays, and a target number.

How can I write a function that returns true if the target number can be made by adding any number from the first array to any number from the second array, and false otherwise?

The following example works, but I would like a more optimized solution.

var a = [1, 2, 3], b = [10, 20, 30, 40];

function sumOfTwo(a, b, v) {
  b = b.sort();

  for (var i = a.length - 1; i > 0; i--) {
    if (b.indexOf(v - a[i]) >= 0) {
      return true;
    }
  }
  return false
}

console.log(sumOfTwo(a, b, 42)); // true
console.log(sumOfTwo(a, b, 44)); // false

Thank you.

Answer 1

You can use this.

function sumMakes(a, b, v) {
    for(var i = 0; i < a.length; i++) {
        for(var j = 0; j < b.length; j++) {
            if(a[i] + b[j] == v) {
                return true;
            }
        }
    }
    return false;
}

Answer 2

You could use a hash table and two loops.

function sumOfTwo(left, right, sum) {
    var hash = Object.create(null),
        i;

    for (i = 0; i < left.length; i++) {
        hash[sum - left[i]] = true;
    }
    for (i = 0; i < right.length; i++) {
        if (hash[right[i]]) {
            return true;
        }
    }
    return false;
}

var a = [1, 2, 3],
    b = [10, 20, 30, 40],
    v = 42;

console.log(sumOfTwo(a, b, 42));

Answer 3

The method you've coded has O(n^2) time complexity since for each element accessed in one array, a call is made to indexOf, which could traverse the entire second array if the target is not found. Here are two methods to perform this check in O(n) time (one of which requires the arrays to be sorted):

1. Store the values from one of the arrays as keys in a hash map (or set). Then iterate over the other array and check if the key, (sum - a[i]), is in the hash map.

2. Given two sorted arrays, use two pointers, one starting at the end of one array, and the other starting at the beginning of the second array. If the sum is too small, increment the pointer that started at the beginning of one array. Otherwise, if the sum is too large, decrement the pointer that started at the end of the second array.

Answer 4

This method assumes sorted data because the example data provided is sorted. If the data is not sorted, you would need to remove the "greater than" check from the second loop.

• If the second array is shorter than the first, swap the arrays.
• Iterate the first array, On each iteration:
  • Initialize a variable to the value of v minus the value of the current element.
  • Iterate the second array, on each iteration:
    • if the value of the current element is greater than the previously stored value, break the loop.
    • if the value of the current element is equal to the previously stored value, return true
  • If no matching values are found, return false

const a = [1, 2, 3], b = [10, 20, 30, 40]

const sumOfTwo = (a, b, v) => {
  if (a.length > b.length) var b = t = a, a = t
  var vnum, ai, bi, al = a.length, bl = b.length
  for (ai = 0; ai < al; ai++) {
    vnum = v - a[ai]
    for (bi = 0; bi < bl; bi++) {
      if (b[bi] > vnum) break
      if (b[bi] == vnum) return true
    }
  }
  return false
}

// This is tests the function based on every integer from 1, 49
new Int32Array(50).forEach((e, i) => console.log(i, sumOfTwo(a, b, i)))

Benchmarks

I have included two benchmarks that include all of the examples provided so far. One with sorted data, and one with unsorted data. An example of the results generated by each benchmark on my computer (Chrome stable on a Windows 7 desktop) will be shown above each snippet, but I encourage you to run the benchmarks to see if you get different results on your computer.

The benchmarks will be run multiple times. Each benchmark will use two input arrays and an incrementing input number. One array will be defined as [1,3,5,7,9], and the other array will be defined as having 100, 1000, 10000, 100000, and 1000000 elements respectively of the benchmark being run. The elements in the second array will be incremented by 10.

Multiple benchmarks are run due to the fact that a given algorithm will have better performance at a given number of elements than it may at others.

The examples will be in the following format:

["String", Boolean, Number, Number, Number, Number, Number]

• The first element is the handle of the author for that example.
• The second element is whether or not the example provides the correct result.
• The remaining Number elements are the operations per second where the second array has 100, 1000, 10000, 100000, and 1000000 elements respectively

The example with the highest operations per second is the fastest example for that dataset.

For the following tests I had to modify @FatihYavus's example slightly to return the correct result, and I had to extract @גלעדברקן's example from this JSPerf link because they did not include that example in their answer.

Sorted Data

["גלעד ברקן",  true, 2596321, 2564350, 26323,  2305,   264]
["Tiny Giant",  true,  428615,   57129, 35887, 35855, 35788]
["Fatih Yavuz", true,  483956,   63193,  8946,   927,    92]
["Nina Scholz", true,  257122,   47083,  9479,  1472,   188]

const benchmark = (name, func) => new Promise((resolve, reject) => setTimeout(() => {
  const test = func => {
    const a = [1, 2, 3], b = [10, 20, 30, 40]
    const testArrayFactory = (m, e, i, arr) => Object.assign(arr, { [i]: func(a, b, i) })
    const testCheck = (e, i) => e === [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0][i]
    return new Int32Array(50).reduce(testArrayFactory).every(testCheck)
  }
  const inputArrayFactory = (m, e, i, a) => Object.assign(a, { [i]: i * 10 })
  const a = [1, 3, 5, 7, 9], m = 1000, r = [name, test(func)]
  for(let i = 2; i < 7; ++i) {
    const b = new Int32Array(10**i).reduce(inputArrayFactory), s = performance.now()
    let ops = 0
    while (performance.now() - s < m) func(a, b, ops++)
    r.push(parseInt((ops * m) / (performance.now() - s)))
  }
  resolve(r)
}))

const funcs = {
  "גלעד ברקן": (arr1,arr2,num) => {
    var p1 = 0, p2 = arr2.length - 1;

    while (p1 < arr1.length && p2 > -1){
      if (arr1[p1] + arr2[p2] === num)
        return true;
      if (arr1[p1] + arr2[p2] < num)
        p1++;
      else
        p2--;
    }
    return false;
  },
  "Tiny Giant": (a, b, v) => {
    if (a.length > b.length) var b = t = a, a = t
    var vnum, ai, bi, al = a.length, bl = b.length
    for (ai = 0; ai < al; ai++) {
      vnum = v - a[ai]
      for (bi = 0; bi < bl; bi++) {
        if (b[bi] > vnum) break
        if (b[bi] == vnum) return true
      }
    }
    return false
  },
  "Fatih Yavuz": (a, b, v) => {
    for (var i = 0; i < a.length; i++) {
      for (var j = 0; j < b.length; j++) {
        if (a[i] + b[j] == v) {
          return true;
        }
      }
    }
    return false;
  },
  "Nina Scholz": (left, right, sum) => {
    var hash = Object.create(null), i;
    for (i = 0; i < left.length; i++) {
      hash[sum - left[i]] = true;
    }
    for (i = 0; i < right.length; i++) {
      if (hash[right[i]]) {
        return true;
      }
    }
    return false;
  }
}

for (let key in funcs) benchmark(key, funcs[key]).then(v => console.log(JSON.stringify(v)))

Unsorted Data

This benchmark uses arrays that have been shuffled using the example provided in How to randomize (shuffle) a JavaScript array?

["גלעד ברקן",  true,  84753,  7534,   174,   10,   1]
["Tiny Giant",  true, 733737,105199, 13473, 1440, 133]
["Fatih Yavuz", true, 488651, 63840,  8349,  812,  78]
["Nina Scholz", true, 225331, 41079,  6898, 1137, 115]

// https://stackoverflow.com/a/2450976/4639281
function shuffle(array) {
  var currentIndex = array.length, temporaryValue, randomIndex;
  while (0 !== currentIndex) {
    randomIndex = Math.floor(Math.random() * currentIndex);
    currentIndex -= 1;
    temporaryValue = array[currentIndex];
    array[currentIndex] = array[randomIndex];
    array[randomIndex] = temporaryValue;
  }
  return array;
}

const benchmark = (name, func) => new Promise((resolve, reject) => setTimeout(() => {
  const test = func => {
    const a = [1, 2, 3], b = [10, 20, 30, 40]
    const testArrayFactory = (m, e, i, arr) => Object.assign(arr, { [i]: func(a, b, i) })
    const testCheck = (e, i) => e === [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0][i]
    return new Int32Array(50).reduce(testArrayFactory).every(testCheck)
  }
  const inputArrayFactory = (m, e, i, a) => Object.assign(a, { [i]: i * 10 })
  const a = shuffle([1, 3, 5, 7, 9]), m = 1000, r = [name, test(func)]
  for(let i = 2; i < 7; ++i) {
    const b = shuffle(new Int32Array(10**i).reduce(inputArrayFactory)), s = performance.now()
    let ops = 0
    while (performance.now() - s < m) func(a, b, ops++)
    r.push(parseInt((ops * m) / (performance.now() - s)))
  }
  resolve(r)
}))

const funcs = {
  "גלעד ברקן": (arr1,arr2,num) => {
    var p1 = 0, p2 = arr2.length - 1;
    arr1 = arr1.sort((a, b) => a - b);
    arr2 = arr2.sort((a, b) => a - b);

    while (p1 < arr1.length && p2 > -1){
      if (arr1[p1] + arr2[p2] === num)
        return true;
      if (arr1[p1] + arr2[p2] < num)
        p1++;
      else
        p2--;
    }
    return false;
  },
  "Tiny Giant": (a, b, v) => {
    if (a.length > b.length) var b = t = a, a = t
    var vnum, ai, bi, al = a.length, bl = b.length
    for (ai = 0; ai < al; ai++) {
      vnum = v - a[ai]
      for (bi = 0; bi < bl; bi++) {
        // if (b[bi] > vnum) break
        if (b[bi] == vnum) return true
      }
    }
    return false
  },
  "Fatih Yavuz": (a, b, v) => {
    for (var i = 0; i < a.length; i++) {
      for (var j = 0; j < b.length; j++) {
        if (a[i] + b[j] == v) {
          return true;
        }
      }
    }
    return false;
  },
  "Nina Scholz": (left, right, sum) => {
    var hash = Object.create(null), i;
    for (i = 0; i < left.length; i++) {
      hash[sum - left[i]] = true;
    }
    for (i = 0; i < right.length; i++) {
      if (hash[right[i]]) {
        return true;
      }
    }
    return false;
  }
}

for (let key in funcs) benchmark(key, funcs[key]).then(v => console.log(JSON.stringify(v)))