JavaScript Determine if Number is Lucky

Question

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?

• AJD: 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.
• MadHatter: Thank you; some up-vote love would be greatly appreciated.

Answer 1

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}