Hexadecimal's Numbers

Observation 1

A number is stored successfully iff its decimal digits are only from the set $\{0,1\}$.

So we are counting:

$$\#\{x \mid 1 \le x \le n,\ \text{every decimal digit of } x \text{ is } 0 \text{ or } 1\}.$$

That sounds like it wants some clever digit DP nonsense... but honestly, no. That would be overkill as hell.

Observation 2: there are almost no candidates

Suppose a valid number has exactly $k$ digits.

• Its first digit must be $1$ (otherwise it would start with $0$, which is not a valid decimal representation of a positive integer).
• Each of the remaining $k-1$ digits can be either $0$ or $1$.

So the number of valid $k$-digit numbers is

$$2^{k-1}.$$

Since $n \le 10^9$, we only need to care about numbers with at most $10$ digits. Therefore the total number of candidates is at most

$$\sum_{k=1}^{10} 2^{k-1} = 2^{10}-1 = 1023.$$

That is microscopic. You can brute-force this without breaking a sweat.

How to generate them

Build valid numbers by appending digits.

From a current valid number $x$, the next valid numbers are:

$$10x \quad\text{and}\quad 10x+1.$$

Why? Because those are exactly the numbers formed by adding a decimal digit $0$ or $1$ at the end.

Start from $1$, then recursively generate:

• $1$
• $10, 11$
• $100, 101, 110, 111$
• and so on.

This naturally forms a DFS/BFS tree.

Important pruning

If at some point $x > n$, we can stop exploring that branch.

Why is that safe? Because appending more digits only increases the number:

$$10x > x, \qquad 10x+1 > x.$$

So every descendant of a too-large number is also too large.

Correctness sketch

We need to show that the DFS counts exactly the required numbers.

1. Every counted number is valid

We start from $1$, whose decimal representation uses only digit $1$. Each transition replaces $x$ by either $10x$ or $10x+1$, which appends a decimal digit $0$ or $1$. So every generated number has only digits from $\{0,1\}$.

2. Every valid number $\le n$ is generated

Take any valid positive integer $y$ whose decimal representation contains only $0$ and $1$. Its first digit must be $1$, and then each following digit is obtained by appending either $0$ or $1$. So starting from $1$ and following those digits, the DFS must reach $y$.

3. No valid number is generated twice

Every generated number has a unique parent: remove its last decimal digit. So the DFS tree has no duplicates.

Putting it together, the algorithm counts each valid number in $[1,n]$ exactly once. Done. Clean. No circus.

Complexity

The number of generated states is at most

$$\sum_{k=1}^{10} 2^{k-1} = 1023.$$

So:

• Time: $O(1023) = O(1)$ in practice
• Memory: $O(10)$ recursion depth

That’s absurdly small. Your CPU won’t even notice this problem happened.