Largest Fancy Number At Most N

Worked Solution

How to Think About It: Fancy numbers -- integers whose base-4 digits are all in $\{0, 1\}$ -- are in bijection with binary strings: read a fancy number's base-4 digits as bits and you get a unique natural number, and vice versa.

The heuristic for "largest X $\leq N$ with a digit constraint" is a greedy left-to-right scan: match $N$'s digits for as long as they are legal, and the first illegal digit decides everything. The key simplification here -- and the step many solutions overcomplicate -- is that no branching or backtracking is ever needed. You might worry that at a digit equal to 1 you should also consider dropping it to 0 (freeing the suffix to be all 1s). You never should: that dropped candidate equals $\text{prefix} + \underbrace{11\cdots1_4}_{r \text{ ones}} = \text{prefix} + \tfrac{4^r - 1}{3}$, which is *strictly less* than $\text{prefix} + 4^r$, the smallest value any tight continuation can reach. Staying tight always ends at something at least that large (either $N$ itself, or a later clamp that keeps this 1 in place), so the dropped candidate can never win. Greedy dominance kills the branch.

Quick Estimate: $N = 100 = 1210_4$. Scan: $1$ (keep), $2$ (illegal -- clamp here). Answer $= 11\,11_4$: keep the leading 1, clamp the 2 down to 1, fill with 1s $= 64 + 16 + 4 + 1 = 85$. Matches the expected output with zero bookkeeping.

Algorithm:

1. Write $N$ in base 4 as $d_k d_{k-1} \cdots d_0$ (most significant first). 2. Walk left to right, keeping a running prefix value. At position with $r$ digits remaining after it: - If $d_i \in \{0, 1\}$: keep it (add $d_i \cdot 4^r$ to the prefix) and continue. - If $d_i \geq 2$: clamp this digit to 1 and fill the rest with 1s. Return $\text{prefix} + 4^r + \tfrac{4^r - 1}{3}$ immediately. 3. If the scan finishes, every digit of $N$ is 0 or 1, so $N$ itself is fancy -- return $N$.

Why the clamp is optimal: any fancy number sharing the prefix is at most the clamped value, and any fancy number that deviates from the prefix earlier had to turn some 1 into a 0, making it strictly smaller. So the first position where $N$'s digit is $\geq 2$ (if any) pins down the whole answer.

Code:

```python def largest_fancy(N: int) -> int: # Base-4 digits of N, most significant first digits = [] tmp = N while tmp > 0: digits.append(tmp % 4) tmp //= 4 digits.reverse()

k = len(digits) prefix = 0 for i, d in enumerate(digits): r = k - i - 1 # digits remaining after position i if d <= 1: prefix += d * (4 ** r) # keep the digit, stay tight else: ones = (4 ** r - 1) // 3 # base-4 '11...1' with r ones return prefix + 4 ** r + ones # clamp to 1, fill with 1s

return N # every digit was 0/1 -- N is already fancy ```

Verified by brute force against direct enumeration for all $N \leq 2 \times 10^5$: exact agreement.

Complexity: $O(\log_4 N) = O(\log N)$ time, one pass; $O(\log N)$ space for the digits.

Answer: One greedy pass over $N$'s base-4 digits. Keep digits while they are 0 or 1; at the first digit $\geq 2$, clamp it to 1 and fill the suffix with 1s; if no such digit exists, $N$ is fancy. No candidate tracking or branching is needed -- dropping a 1 is always dominated by staying tight.