2
\$\begingroup\$

A challenge from Code Fights; a function that takes a number no less than 10 and that will always have an even number of digits and determines if the sum of the first half of the digits equals the sum of the second half of digits. The function returns a Boolean. Maximum execution time is 4000 milliseconds.

Here is the function:

// tickets are lucky when sum of first half equals sum of second half
const isLucky = n => {
  // min is 10 and we know it's false
  if (n === 10) return false;
  // store digits in an array
  const digitCorral = [];
  // use modulo, division and Math.trunc
  while (n > 0) {
    // push reverses the order but that doesn't matter
    // since the sum of each half will still be the same
    digitCorral.push(n % 10);
    n /= 10;
    n = Math.trunc(n);
  }
  // get sum of first half of array
  const firstHalf = digitCorral
    .slice(0, digitCorral.length / 2)
    .reduce(function(a, b) {
      return a + b;
    });
  // get sum of second half of array
  const secondHalf = digitCorral
    .slice(digitCorral.length / 2, digitCorral.length)
    .reduce(function(a, b) {
      return a + b;
    });
  // return a boolean
  return firstHalf === secondHalf;
};

The function passes all tests, however, I wonder if there is an even more efficient way write it--would recursion be faster? Can the speed of this algorithm be improved?

\$\endgroup\$
  • 1
    \$\begingroup\$ Don't know javascript so cannot comment/review the code. An alternative, take number as a string (doesn't matter if string or array of single-digit numbers) and then in a single loop start adding from the front and the back at the same time (VBA:For j = 1 to lenInput/2: sum1 = sum1 + input(j): sum2 = sum2+ input(lenInput-j): next j: result = sum1=sum2). I can't see how recursion would be any more efficient in this case and probably has more overhead. \$\endgroup\$ – AJD Jul 17 '18 at 20:07
  • \$\begingroup\$ Thank you; some up-vote love would be greatly appreciated. \$\endgroup\$ – MadHatter Jul 17 '18 at 20:15
1
\$\begingroup\$

Bad storage and time

Your code solves the problem but is a memory hog.

Algorithm complexity

You are looping over the digits twice, once to extract each digit, and then once to sum each half. The logic can be improved if you calculate the sums as you extract each digit. This also means you do not have to store each digit in the array for the sum calculations.

If you include the two Array.slice calls that is a total of 3 iteration of each digit in n and two stored copies of each digit.

JavaScript performance

In terms of JavaScript performance array functions that take callbacks, like Array.reduce, have a high per iteration overhead when compared to standard loops. When the inner code is small that overhead is a significant part of the overall iteration time.

Array.slice should only be used when you need a copy of items in a new array. (Note items that are references only copy the reference. IE shallow copy).

Arrays in JavaScript are expensive in terms of performance because they do not get space from the heap but rather invoke the memory management system for allocation and disposal.

Code style

  • Never create un-delimited blocks. if (n === 10) return false; should be if (n === 10) { return false; } or if (n === 10) { return false }

  • The reduce callback is written in the long form, .reduce(function(a, b) { return a + b }) it would be less noisy to write it as .reduce((a, b) => a + b)

  • Too many comment, and one that conflicts with the code (a lie).

Apart from that the code is well formatted, has good naming, and good use of variable declaration type.

Your question

would recursion be faster?

Seldom is recursion faster. Recursion is used to simplify state stack management, the function call is the state push, and return the state pop.

Until tailcalls are implemented in JavaScript, functions that are O(1) storage, become O(n) storage if converted to recursive solutions. There is no time complexity change. The solution is a O(1) storage problem and thus will not benefit from recursion.

I wonder if there is an even more efficient way write it

Yes there is, see bottom rewrite.

Rewrites

Using your algorithm and API use.

Comment are only added as I am not sure if you recognize the code or why.

The test for 10 is not worth the cost [1]

const isLucky = n => {
    const sum = (a, b) => a + b; // minor memory/parse gain with one rather than two functions 
    const digitCorral = [];
    while (n > 0) {
        digitCorral.push(n % 10);
        n = n / 10 | 0;  // Bitwise OR 0 is the faster form of Math.trunc
    }
    const first = digitCorral
        .slice(0, digitCorral.length / 2)
        .reduce(sum);
    const second = digitCorral
        .slice(digitCorral.length / 2)
        .reduce(sum);
    return first === second;
}

A better way.

Improved with O(1) storage, O(n) complexity where n is the number of digits in argument n

const isLucky = n => {    
    var midDigit, n1, sum1 = 0, sum2 = 0;
    midDigit = (Math.log10(n) + 1 | 0) >> 1;
    const midMod = 10 ** midDigit;
    n1 = n / midMod | 0;
    n %= midMod;
    while (midDigit --) {
        sum1 += n % 10;
        sum2 += n1 % 10;
        n = n / 10 | 0;
        n1 = n1 / 10 | 0;
    }
    return sum1 === sum2;
}

1. The following calculations are orders of magnitude approximations only. The early exit test for 10 (about 1/100 operations) is only worth the CPU time if there is a high probability of 10. That's a cost of 1% of operations, for gain of 1e-7%. The gain should always outweigh the cost by at least one order. That will only happen when 10 is about 100Million times more likely than any other number

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.