# 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 | function getEulerUpToNumber(ceiling) { |

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 | function getEulerOnSpeed(ceiling) { |

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!

## What did we learn?

- Mathematics is brilliant.
- JavaScript? Not so much.
- Use
`BigInt`

or a same-case library to deal with large numbers.