https://www.codingame.com/training/medium/bit-count-to-limit

Send your feedback or ask for help here!

Created by @DPAmar,validated by @tutubalin,@CyberLemonade and @cg123.

If you have any issues, feel free to ping them.

https://www.codingame.com/training/medium/bit-count-to-limit

Send your feedback or ask for help here!

Created by @DPAmar,validated by @tutubalin,@CyberLemonade and @cg123.

If you have any issues, feel free to ping them.

My stupid bruteforce solution passes all testcases but fails on the last submit validator. Iām outraged .

On a more serious note: the validators should not be harder than their corresponding testcases.

5 Likes

Itās not. As I stated in the problem comments : a damn fast O(n) implementation may solves all the test cases, including validators. But itās not the goal, obviously : there is a O(ln(n)) one

N from last validator is as complex as the corresponding TC (id est : it is encoded over the same number of bits)

1 Like

Iām aware of the existence of a faster solution than O(n). I just thought Iāll give it a shot with O(n) anyways to see if I can pass. And I did so on the visible testcases (I can share my code via private message if you want). On submit however I had an unpleasant surprise.

Iām not complaining about not passing with my slow approach. In fact this code should not pass IMO. Iām suggesting to increase the input for the visible testcase to make it bigger than the corresponding validator.

The N of the validator is larger, making it harder for a bruteforce solution. For my code the 1s timelimit given my CodinGame is somewhere between the testcase and validator.

1 Like

As I said, goal was to find a log(N) version. I this configuration, there is no difference between last TC and validator (same complexity)

I tried to find some brute force code that would pass last TC but failed. I posted a brute force C solution that is indeed able to go through last TC in about 2 seconds (interested in a faster solution BTW ) But this is anyway too long for CG

If that is the goal, please make it apparent * and tested* in the visible set.

1 Like

Donāt get your point.

Aynway. It appears that the same bruteforce implementation

- fails last TC nor validator in C
- passes last TC but not last validator in C#
- passes both last TC and last validator in JS

ā¦

Yes, the goal actually is to find a smart implementation. Hence, the TC title āDid you get the trick ?ā.

And yes, this **has been tested**. Again, using C. How am I supposed to guess the counter-intuitive fact that JS would have been faster ???

The point is itās bad practice to have validators be strictly harder than tests. Itās a simple guideline, and it avoids that class of failure.

What does harder mean, then?

Considering logarithmic complexity, a 28-bit-long integer is no more complex than any other 28-bit-long integer, is it?

I havenāt solved it so I theoretically donāt know what itās about, but obviously @eulerscheZahl found a ānaturalā counterexample. On an O(N) solution, any N can be presumed āharderā than a lower N. Which seems to be the case for this puzzle, considering his suggestion.

So it seems: just increasing n in the ide test and decreasing it in the validator would make everyone happyā¦

By the way, nice puzzle, congrats, very much liked it: very simple to understand, very simple to code, yet it still needed some brainwork (for the O(log n) I meanā¦). I recommend to put it under āeasyā instead of āmediumā, this is a <5 min puzzle. But itās up to you.

Ok, Iāve tried it.

And solved it much quicker than expected because my O(N) algorithm passed both tests and validators on first try.

So very easy indeed, a straightforward statement implementation does it.

I donāt know if any of the 20+ languages supported on CG has problem with 64 bit integers. If not, then brute force could be ruled out with a e.g. 58-bit test case (or whatever is the max so that also the result is below <64 bits(

I donāt think that there should be such game-breaking changes after the approval of a puzzle. Thatās what the review phase is good for. Javascript only has doubles, no integers.

I donāt understand how can your āstupid brute forceā be O(n) complexity. If you check and add-up 1-digit counts for all numbers 1 to n, for each individual number you still need to add the 1s - that is O(log(n)). So in total āstupid brute forceā is O(n*log(n)) and not O(n). Otherwise it is already not that āstupidā

But I understand that in a practical, 64bit limit range, O(n) and O(n * log n) is essentially the same, although mathematically different.

@TBali Youāre right of course (we could even say the complexity is ā log i = log n! = O(n log n)).

That said, the number of ones can also be counted in O(result) as follows:

```
def ones(n):
cnt1 = 0
while n:
cnt1 += 1
n &= n-1
return cnt1
```

My language (and CPU) have a constant-time bit-count operation. So Iām constant-time per number (within 64 bits), and constant-time per addition. Ī(N), as long as lgN<64.

Indeed. My solution would degrade to Ī(NĆlgN) if I allowed it to exceed 64-bit inputs.

@JBM Well, if you consider log N as a constant, then N is also a constant and it falls down to O(1).

~~Iāll edit.~~ Edited.

This message will self-destruct tomorrow.

And still there is an O(n) solution:

```
def count(val, ones):
if val > limit: return
solution += ones
count(2*val, ones)
count(2*val+1, ones+1)
count(1, 1)
```

2 Likes