Skip to main content
added 13 characters in body
Source Link
Blindman67
  • 22.9k
  • 2
  • 17
  • 40
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;
 
};
const isLucky = n => {    
    letvar midDigit, n1, sum1 = 0, sum2 = 0;
    midDigit = (Math.log10(n) + 1 | 0) >> 1;
    const midMod = 10 ** midDigit;
    let n1 = n / midMod | 0;
    n %= midMod;
    let sum1 = 0, sum2 = 0;
    while (midDigit --) {
        sum1 += n % 10;
        sum2 += n1 % 10;
        n = n / 10 | 0;
        n1 = n1 / 10 | 0;
    }
    return sum1 === sum2;
}
const isLucky = n => {
    const sum = (a, b) => a + b; // minor memory/parse gain with one rather than two 
    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;
 
};
const isLucky = n => {    
    let midDigit = (Math.log10(n) + 1 | 0) >> 1;
    const midMod = 10 ** midDigit;
    let n1 = n / midMod | 0;
    n %= midMod;
    let sum1 = 0, sum2 = 0;
    while (midDigit --) {
        sum1 += n % 10;
        sum2 += n1 % 10;
        n = n / 10 | 0;
        n1 = n1 / 10 | 0;
    }
    return sum1 === sum2;
}
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;
}
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;
}
Source Link
Blindman67
  • 22.9k
  • 2
  • 17
  • 40

#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 
    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 => {    
    let midDigit = (Math.log10(n) + 1 | 0) >> 1;
    const midMod = 10 ** midDigit;
    let n1 = n / midMod | 0;
    n %= midMod;
    let sum1 = 0, sum2 = 0;
    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