A ledger validator flags each integer by the parity of its Hamming weight (the number of 1 bits). An integer is called balanced when its number of set bits is even (0 counts as even).
Given n, count how many integers x with 1 <= x <= n are balanced (have an even number of set bits).
Line 1: an integer n.
A single integer: the count of integers in [1, n] whose set-bit count is even.
Example 1
Input
5
Expected
2
Explanation
In 1..5 the set-bit counts are 1,1,2,1,2; the balanced values are 3 and 5, so the answer is 2.
Example 2
Input
1
Expected
0
Explanation
Only 1, which has one set bit (odd), so there are 0 balanced values.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →