3
\$\begingroup\$

I wrote a function that finds the sum of all numeric palindromes lesser than N.

const sumOfPalindromes = (n) => {
    let x = 0;
    for (let i = 0; i <= n; i++) {
      x += i == (''+i).split('').reverse().join('') ? i : 0;
    }
    return x;
}

console.log(sumOfPalindromes(10000));
console.log(sumOfPalindromes(24));

Are there shorter, more-concise alternatives to the above approach (preferably without using a for loop)?

\$\endgroup\$
2
  • \$\begingroup\$ Your implementation is 1 off for any n that is a palindrome because i <= n does not implement the "lesser then n" predicate, it implements "lesser or equal". Btw is 1.1 a numeric palindrome? \$\endgroup\$
    – slepic
    Jul 3 '20 at 3:22
  • \$\begingroup\$ @slepic I completely missed that. Thanks for pointing that out. And no, floats are not included. \$\endgroup\$
    – AndrewL64
    Jul 3 '20 at 11:21
4
\$\begingroup\$

This is not a proper review, but rather an extended comment.

Are there shorter, more-concise alternatives to the above approach

Yes. You should view it not as a programming problem, but as a recreational math exercise.

Consider a simplest case of N being an even power of 10, say 1000000. For a moment, allow leading zeroes. Now, each 6-digit palindromic number abccba corresponds to a 3-digit number abc, and in fact is 1000*abc + cba. Notice that if the sum of all 3-digit numbers is X, the sum of all 6-digit palindromic numbers is 1000*X + X = 1001*X. As for X, recall the formula for the sum of an arithmetic progression 0 + 1 + 2 + ... + 999.

To deal with leading zeroes you must subtract the sum of those palindromic numbers which do have leading zeroes. Yet again, they are in form abba0 = 1000*ab + 10*ba. Yet again, use the arithmetic progression formula to get the result.

No programming beyond a few arithmetic operations is required.

I don't want to spell out the complete solution. I hope this is enough to get you started with the arbitrary N.

\$\endgroup\$
3
\$\begingroup\$

The function you posted seems to me to be the best. Here is your function re-arranged slightly using short-circuiting as an alternative way:

const sumOfPalindromes = n => {
        let x = 0;
        for (let i = 0; i <= n; i++)
        i == (''+i).split('').reverse().join('') && (x += i);
        return x };

console.log(sumOfPalindromes(10000));
console.log(sumOfPalindromes(24));

\$\endgroup\$
3
\$\begingroup\$

"numeric palindromes" is rather unfortunate term. It is not clear if nonintegers are to be considered. The implementation only considers integers, in which case i would rather use term "palindromic integers".

It is also not explicitly stated, although assumed, that only base 10 representations are to be considered. Some numbers that are not palindromic in base 10 may be palindromic in different bases. I would actualy say that every nonnegative integer is palindromic in infinte amount of various bases. And so even a better term might be "palindromic base 10 integers".

preferably without using a for loop

That is a silly requirement, you could do it with reduce but that would require to first create an array of all the numbers less then n. Which would increase the memory complexity of the implementation to O(n) for no real benefit. And it will probably be slower, although the big-O time complexity stays the same.

To be complete the current memory complexity Is O(log(n)). And time complexity is O(n * log(n)), or more precisely O(log(n!)).

Since you are not asking to improve performance, but rather to shorten the code (and that's perfectly fine if you dont pass large n's and dont call the function many times in a loop) , I would say you are pretty good with your current implementation.

I would just replace the ternary with an if because adding zero is a useless operation.

And there is a bug in your implementation where the result is by 1 greater then it should be if the input n is a palindrome. You should do i < n instead of i <= n.

If you want to improve the time complexity, you need to do some maths as @vnp already suggested. Intuition tells me you might end up with time complexity O(log(n)) and that will be a big improvement for bigger n's compared to your current O(log(n!)) implementation.

\$\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.