[Community Puzzle] Bit count to limit

@JBM What I meant was that if you consider the numbers are written on a bounded number of bits, then they are themselves bounded, so the actual complexity can only be O(1). But indeed in practice everybody understands why we say O(N) here.

@eulerscheZahl Indeed (even though it goes up to the next power of 2).

Yes, I understood you properly on the first try :smiley:

Higher than that: 2×limit + 1

@JBM Indeed, my bad.

I know this is late to the party but this is what I observed in Dart. If you try Brute Force, like other languages, you can get through the first couple of tests but fail at the last one. So I implemented the “trick” (powers of 2) method and this gets me through all tests easily. HOWEVER, on submission, you fail the last validator. My assumption then is – even though the trick still works (in other words, just keep going up powers of 2 – the number for the last validator must be so large that (in Dart), I need to switch storage types. Again, I’m assuming, I now must use BigInt instead of int. If that’s the case, I agree with JBM, not that the validator is necessarily harder, but it’s actually a new problem that isn’t exposed during the tests. I’ll code BigInt and see if that works but that’s my two cents: obviously something different happens in the validator and in general, I don’t think that is fair to the solver.

3 Likes

Puzzle is painful to solve at the beginning. The hardest is to pass the last validator even if the 5 tests are passed. I have found and used an O(log n) solution, but it works in Swift (might be the same in other languages) if unsigned integer is used (UInt). Also, CodinGame server plateform is on 64 bits, so UInt is on 64-bits and it’s useful to avoid overflow and pass the last validator. With Int, it fails at validator 5.

At least folks should be able to see the optimized answer or hints if they are stumped by the optimization part.Don’t see why anyone would try if they can’t even see an answer.