9CUnreviewed1200GPT-5.4 (high)

Hexadecimal's Numbers

Progressive hints first, then the full explanation and implementation when you're ready to cash out.

brute force implementation math

Original problem

Review status

AI-generated and still unreviewed. Double-check the details before internalizing them.

Hints

Progressive nudges

Open only as much as you need to keep the solve alive.

Try ignoring the story fluff: you only need to count numbers in $[1,n]$ whose decimal representation uses only digits $0$ and $1$ . How many such numbers can there even be when $n \le 10^9$ ?

For a fixed length $k$ , the first digit cannot be $0$ , so it must be $1$ . Every remaining digit can be chosen independently from $\{0,1\}$ . That gives $2^{k-1}$ valid numbers of length $k$ .

Now sum over all possible lengths. Since $n \le 10^9$ , you only care about lengths up to $10$ , so the total number of candidates is tiny: $\sum_{k=1}^{10} 2^{k-1} = 1023.$ That’s small enough to just generate everything and count.

Think of a tree of valid numbers: from a number $x$ , appending a digit $0$ or $1$ gives children $10x \quad\text{and}\quad 10x+1.$ Start from $1$ and explore recursively or with a queue.

Do a DFS/BFS starting from $1$ . Whenever you see a number $x \le n$ , count it, then try $10x$ and $10x+1$ . If $x>n$ , stop immediately because appending more digits only makes it larger. Use long long, because $10x$ can briefly exceed $10^9$ .

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.

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

int main() {
    setIO();

    ll n;
    cin >> n;

    ll ans = 0;

    function<void(ll)> dfs = [&](ll x) {
        if (x > n) return;
        ++ans;
        dfs(x * 10);
        dfs(x * 10 + 1);
    };

    dfs(1);

    cout << ans << '\n';
}

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

int main() {
    setIO();

    ll n;
    cin >> n;

    ll ans = 0;

    function<void(ll)> dfs = [&](ll x) {
        if (x > n) return;
        ++ans;
        dfs(x * 10);
        dfs(x * 10 + 1);
    };

    dfs(1);

    cout << ans << '\n';
}

View on Codeforces Back to the list

Hexadecimal's Numbers

Progressive nudges

Full explanation

Observation 1

Observation 2: there are almost no candidates

How to generate them

Important pruning

Correctness sketch

1. Every counted number is valid

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

3. No valid number is generated twice

Complexity

Generated C++

Hexadecimal's Numbers

Progressive nudges

Full explanation

Observation 1

Observation 2: there are almost no candidates

How to generate them

Important pruning

Correctness sketch

1. Every counted number is valid

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

3. No valid number is generated twice

Complexity

Generated C++

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