Count Base-4 Numbers of Zeros and Ones
MediumMath ยท HRT
Return how many positive integers smaller than n use only the digits 0 and 1 when written in base 4.
Example 1
- Input:
- n = 10
- Output:
- 3
- Explanation
- The qualifying numbers are 1, 4 (
10) and 5 (11).
Example 2
- Input:
- n = 5
- Output:
- 2
- Explanation
- 5 qualifies but is not smaller than
n, so only 1 and 4 count.
Example 3
- Input:
- n = 1
- Output:
- 0
Constraints
1 <= n <= 10^15- The answer fits in a 32-bit integer
- Enumerating every value below
nwill not finish for the largest inputs