Problem Brief

Count Fancy Numbers

INTERNOA

For the original problem description, pls checkout the image source at the very bottom of this web page 🐾🐾

Imagine you’re in a magical world where certain numbers are considered "fancy." A number is fancy if, when written in base-4, it only contains the digits 0 and 1—like secret codes known only to wizards. For example, 17 is fancy because its base-4 form, 101, uses only 0s and 1s, while 18 is not, as its base-4 form, 102, contains a forbidden 2. Now, your task is to discover how many of these special, fancy numbers exist below a given number, n. But beware! n can be as big as a billion, so you need a clever method—something faster than just checking every number individually.

1Example 1

Input

n = 1

Output

Explanation

There are no positive integers less than 1.

2Example 2

Input

n = 10

Output

Explanation

The fancy numbers less than 10 are {1, 4, 5}.

Draft autosaves locally

public int countFancyNumbers(int n) {
  // write your code here
}

Input

Output