JavaScript woes in HackerRank's multiples of 3 and 5 challenge

tl;dr: JavaScript handles large numbers poorly, so HackerRank’s tests break solutions that don’t handle that edge case. Use BigInt or a third-party library when dealing with numbers larger than 2^53.

I’ve been brushing up on my algorithm skills using HackerRank, focusing on exercises that help me conceptualize solutions and focus on Big-O optimizations. The website “imports” the challenges of Project Euler, which is what brought me to this one. However, JavaScript has a major issue with big numbers, which becomes a stress case here.

The challenge is simple: for any given N, find the sum of all multiples of 3 or 5 below N. One of the constraints is that N is never greater than 10^9, which yields a maximum result of 233333333178105280. This is well within the boundaries of 2^53, so what’s wrong?

A basic iterative solution fails 3/6 test cases

I’m going to skip linear recursion because it would have the same time complexity, but have O(n) space complexity.

Still, my iterative solution failed 2 of the 6 test cases and timed-out on 1 of the 6. Unfortunately, HackerRank “blocks” console access in challenges. I was also unable to “unlock” the failing tests cases, getting an HTTP 503. However, at this point we know 2 things:

  • one of the cases is a stress case for time complexity
  • two of the cases are using values that don’t play well with JavaScript’s number system

The iterative approach, with time complexity O(n) and space complexity O(1) is:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function getEulerUpToNumber(ceiling) {
if (ceiling < 3) return 0
if (ceiling <= 4) return 3
if (ceiling === 5) return 3 + 5

let accumulator = 8

for (let i = 6; i < ceiling; i++) {
if (i % 3 === 0 || i % 5 === 0) {
accumulator += i
}
}

return accumulator
}

Some thoughts on those 3 if statements: I’m dealing with the basic cases with ceilings less than or equal to 5. Easy. Given that, I can start the accumulator right at 8. But is it useful? What’s the practical impact of that optimization? It has none. Checking for these 3 first values is just “smart” code that keeps the solution at O(n).

This solution doesn’t 100% work, so I went on a research tangent. The solutions from other languages are the same: iterate up to ceiling, accumulating values that are multiples of 3 or 5. Simple, uh? JavaScipt must be the root of the issue.

Spoilers: it is.

Big league numbers in JavaScript

Fortunately, it’s easy to find the cause of this issue: JavaScript’s handling of large numbers. At this point it doesn’t matter if the issue is floating-point precision or the maximum integer ceiling.

By the way, Number.MAX_SAFE_INTEGER represents the maximum safe integer in JavaScript: (2^53 - 1).

Fortunately, BigInt is a stage-3 proposal which has already been implemented in Node 10.15. Armed with that knowledge, a bleeding-edge TypeScript/Jest config, and some really nasty test cases, we can improve our solution to use BigInt.

Going O(1)

At this stage, for large numbers the iterative approach takes 4 to 10 seconds to finish. However, the time complexity stress case still failed. Can we make it O(1)?

Of course we can. Mathematics finds a way.

Based on the mathematical analysis of the problem, you can arrive at sub-100ms speeds using:

1
2
3
4
5
6
7
8
9
10
11
12
function getEulerOnSpeed(ceiling) {
return euler(BigInt(ceiling - 1))
}

function euler(n) {
return sum(n, BigInt(3)) + sum(n, BigInt(5)) - sum(n, BigInt(15))
}

function sum(n, k) {
const d = n / k
return k * (d * (d + BigInt(1))) / BigInt(2)
}

Using BigInt has the side benefit of getting rid of the Math.floor call on the 2 instructions in the sum function. Aso, please note that I’ve omitted proper TypeScript signatures.

With the solution above, we’re at O(1) time complexity and O(1) space complexity. Perfect!

You've solved Euler's first challenge. Now share this on all the social.

What did we learn?

  1. Mathematics is brilliant.
  2. JavaScript? Not so much.
  3. Use BigInt or a same-case library to deal with large numbers.