A positive integer is "fancy" if its representation in base 4 only includes 0 s and 1 s. For example:
17 is fancy: its base-4 representation, 101 , only includes 0 s and 1 s.
18 is not fancy: its base-4 representation, 102, includes a 2.
Given a positive integer,n , find the number of fancy positive integers less than n
Note that may be as large as a billion! Your algorithm should be faster than iterating over values less than n and checking if each one is fancy.
Example For n, the output should be : there are no positive integers less than 1.
For n=1- ,the output should be since {1,4,5} are all fancy.
input/Output
[execution time limit] 0.5 seconds (cpp)
[input] integer n
An upper bound on the range.
Guaranteed constraint: - 0