javascript - Is there a way to avoid number to string conversion & nested loops for performance?

Question

I just took a coding test online and this one question really bothered me. My solution was correct but was rejected for being unoptimized. The question is as following:

Write a function combineTheGivenNumber taking two arguments:

1. numArray: number[]
2. num: a number

The function should check all the concatenation pairs that can result in making a number equal to num and return their count.

E.g. if numArray = [1, 212, 12, 12] & num = 1212 then we will have return value of 3 from combineTheGivenNumber

The pairs are as following:

1. numArray[0]+numArray[1]
2. numArray[2]+numArray[3]
3. numArray[3]+numArray[2]

The function I wrote for this purpose is as following:

function combineTheGivenNumber(numArray, num) {
  //convert all numbers to strings for easy concatenation
  numArray = numArray.map(e => e+'');
  //also convert the `hay` to string for easy comparison
  num = num+'';
  let pairCounts = 0;
  
  // itereate over the array to get pairs
  numArray.forEach((e,i) => {
    numArray.forEach((f,j) => {
    if(i!==j && num === (e+f)) {
        pairCounts++;
       }
    });
  });
  
  return pairCounts;
}

console.log('Test 1: ', combineTheGivenNumber([1,212,12,12],1212)); 

console.log('Test 2: ', combineTheGivenNumber([4,21,42,1],421)); 

question from:https://stackoverflow.com/questions/65642145/is-there-a-way-to-avoid-number-to-string-conversion-nested-loops-for-performan

Answer 1

I like your approach of going to strings early. I can suggest a couple of simple optimizations.

You only need the numbers that are valid "first parts" and those that are valid "second parts"

You can use the javascript .startsWith and .endsWith to test for those conditions. All other strings can be thrown away.

The lengths of the strings must add up to the length of the desired answer

Suppose your target string is 8 digits long. If you have 2 valid 3-digit "first parts", then you only need to know how many valid 5-digit "second parts" you have. Suppose you have 9 of them. Those first parts can only combine with those second parts, and give you 2 * 9 = 18 valid pairs.

You don't actually need to keep the strings!

It struck me that if you know you have 2 valid 3-digit "first parts", you don't need to keep those actual strings. Knowing that they are valid 2-digit first parts is all you need to know.

So let's build an array containing:

  How many valid 1-digit first parts do we have?,
  How many valid 2-digit first parts do we have?,
  How many valid 3-digit first parts do we have?,
  etc.

And similarly an array containing the number of valid 1-digit second parts, etc.

X first parts and Y second parts can be combined in X * Y ways

Except if the parts are the same length, in which case we are reusing the same list, and so it is just X * (Y-1).

So not only do we not need to keep the strings, but we only need to do the multiplication of the appropriate elements of the arrays.

5 1-char first parts & 7 3-char second parts = 5 * 7 = 35 pairs

6 2-char first part & 4 2-char second parts = 6 * (4-1) = 18 pairs

etc

So this becomes extremely easy. One pass over the strings, tallying the "first part" and "second part" matches of each length. This can be done with an if and a ++ of the relevant array element.

Then one pass over the lengths, which will be very quick as the array of lengths will be very much shorter than the array of actual strings.

function combineTheGivenNumber(numArray, num) {
  const sElements = numArray.map(e => "" + e);
  const sTarget = "" + num;
  const targetLength = sTarget.length
  const startsByLen = (new Array(targetLength)).fill(0);
  const endsByLen = (new Array(targetLength)).fill(0);

  sElements.forEach(sElement => {
    if (sTarget.startsWith(sElement)) {
      startsByLen[sElement.length]++
    }
    if (sTarget.endsWith(sElement)) {
      endsByLen[sElement.length]++
    }
  })
  // We can now throw away the strings. We have two separate arrays:
  // startsByLen[1] is the count of strings (without attempting to remove duplicates) which are the first character of the required answer
  // startsByLen[2] similarly the count of strings which are the first 2 characters of the required answer
  // etc.
  // and endsByLen[1] is the count of strings which are the last character ...
  // and endsByLen[2] is the count of strings which are the last 2 characters, etc.

  let pairCounts = 0;

  for (let firstElementLength = 1; firstElementLength < targetLength; firstElementLength++) {
    const secondElementLength = targetLength - firstElementLength;
    if (firstElementLength === secondElementLength) {
      pairCounts += startsByLen[firstElementLength] * (endsByLen[secondElementLength] - 1)
    } else {
      pairCounts += startsByLen[firstElementLength] * endsByLen[secondElementLength]
    }
  }

  return pairCounts;
}

console.log('Test 1: ', combineTheGivenNumber([1, 212, 12, 12], 1212));
console.log('Test 2: ', combineTheGivenNumber([4, 21, 42, 1], 421));