Sample Input / Output 3 implies that the \(1099898\)-th smallest good integer is \(819264512\approx 0.8 \times 10^9\), so we can infer that there are not so many good integers below \(10^9\). Therefore, we may enumerate all good integers and sort them to retrieve the \(N\)-th element among them.

Since \(10^9\) is not a good integer, it suffices to enumerate good integers with \(9\) digits or less. Let \(X_k\) be the set of good integers with exactly \(k\) digits, and \(P_k\) be the set of powers of two with exactly \(k\) digits. For convenience, let \(X_0=\{0\}\). Then for all \(k\geq 1\):

\[X_k=\bigcup_{i=1}^{k}\left\{x\cdot 10^i+p\mid x\in X_{k-i}, p\in P_i\right\}.\]

The good integers can be enumerated by appropriately implementing the equation above.

By actually enumerating, we find that there are \(1257874\) good integers up to \(10^9\), which can be computed fast enough.

Sample code (Python)

P = [[] for _ in range(10)]
for k in range(1, 10):
    l = (10 ** (k - 1) - 1).bit_length()
    r = (10 ** k - 1).bit_length()
    P[k] = [1 << i for i in range(l, r)]

X = [set() for _ in range(10)]
X[0] = {0}
A = []
for k in range(1, 10):
    for i in range(1, k + 1):
        X[k] |= {x * (10 ** i) + p for x in X[k - i] for p in P[i]}
    A += list(X[k])
A.sort()

N = int(input())
print(A[N - 1])

Estimation of the number

We describe how we can estimate the number of good integers.

We will evaluate the number of good integers with \(k\) digits or less: \(S_k=|X_1|+\cdots+|X_k|\).

Since \(|P_i|\leq \lceil\log_2 10\rceil=4\), for \(k\geq 1\) we have:

\[\begin{aligned} S_k-S_{k-1} &=|X_k|\\ &=\left|\bigcup_{i=1}^{k}\left\{x\cdot 10^i+p\mid x\in X_{k-i}, p\in P_i\right\}\right|\\ &\leq\sum_{i=1}^{k}\left|\left\{x\cdot 10^i+p\mid x\in X_{k-i}, p\in P_i\right\}\right|\\ &=\sum_{i=1}^{k}|X_{k-i}|\cdot |P_i|\\ &\leq 4(|X_{k-1}|+\cdots+|X_1|+|X_0|)=4(S_{k-1}+1). \end{aligned}\]

With this inequality,

\[S_k+1\leq 5(S_{k-1}+1)\leq \cdots \leq 5^k(S_0+1)=5^k,\]

implying that there are at most \(5^k-1\) good integers with \(k\) digits or less. Since \(5^9-1=1953124\) and this is a rough estimation, we can guess that enumerating all of them will finish within the time limit.