Fancy Numbers

A positive integer is "fancy" if its representation in base 4 only includes 0s and 1s.

For example:

• 17 is fancy: its base-4 representation is 101, which only includes 0s and 1s.
• 18 is not fancy: its base-4 representation is 102, which includes a 2.

Problem Statement

Given a positive integer n, find the number of fancy positive integers that are less than n.

Your algorithm should be efficient since n can be as large as a billion. Iterating over values less than n and checking each one is inefficient.

Example

• For n = 1, the output should be 0, since there are no positive integers less than 1.
• For n = 10, the output should be 3, since {1, 4, 5} are fancy numbers.

Input/Output

• Execution Time Limit: 4 seconds (Python 3)
• Memory Limit: 1 GB
• Input: A single integer n representing the upper bound.
• Guaranteed Constraint: 0 < n ≤ 10⁹

我们长期稳定承接各大科技公司如TikTok、Google、Amazon等的OA笔试代写服务，确保满分通过。如有需求，请随时联系我们。

We consistently provide professional online assessment services for major tech companies like TikTok, Google, and Amazon, guaranteeing perfect scores. Feel free to contact us if you're interested.