Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
A decibinary number uses decimal digits (0–9) but positional weights of 2 — so its decimal value is Σ digit_i · 2^i. List every decibinary number ordered first by decimal value, then by the numeral itself, and answer 'what is the x-th number in that list?'. Solve it in two layers: (1) a counting DP — count[b][v] = how many decibinary numerals using bit-positions 0..b evaluate to decimal value v — whose top row gives numWays[v], the count of numerals equal to v; (2) prefix-sum over numWays to binary-search which decimal value d the x-th numeral belongs to, then greedily reconstruct the k-th smallest numeral of value d digit by digit. Counts approach 10^16, so use 64-bit longs (Python ints are unbounded). Precompute once, answer every query in O(log + digits).
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you can design a counting DP over place values, then convert raw counts into an ordinal lookup via prefix sums and greedy digit reconstruction — and whether you spot the 64-bit overflow risk.
Where candidates slip
Trying to enumerate or generate decibinary numbers directly (astronomically many), using int and overflowing, mis-ordering the global list (forgetting value 0 is index 1), or reconstructing digits in the wrong direction.
How to stand out
Separate the two phases cleanly (count, then rank), explain why fixed-width digit order equals numeral order, justify 64-bit, and note that all queries share one O(BITS·MAXV) precompute.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewCounting DP: count[b][v]binary search for value dYesNoExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Brute Force — Enumerate Decibinary Numbers (Infeasible)
1Hint 1Explore hintHide hint
You could march through decimal values 0, 1, 2, … and, for each, generate its decibinary numerals in increasing order, counting until you hit index x.
2Hint 2Explore hintHide hint
Generating one value's numerals means enumerating digit combinations whose weighted sum equals the value — itself expensive.
3Hint 3Explore hintHide hint
Since x reaches 10^16, walking the list one numeral at a time is hopeless even for a single query.
A · Core idea
The most literal solution: iterate decimal values upward; for each value, list its decibinary numerals smallest-first; keep a running counter; when the counter reaches x, emit the current numeral.
Why it's correct. It walks the exact list the problem defines, so it returns the right numeral.
Why it's hopeless. Two compounding costs. First, the index x can be 10^16, so even an O(1)-per-numeral walk would take 10^16 steps for one query. Second, generating the numerals of a single value already means enumerating digit assignments that sum (with binary weights) to that value — exponential in the number of positions. Multiply by up to 10^5 queries and it's nowhere near feasible.
The lesson. We never actually need the numerals before index x — we only need how many there are, so we can skip whole value-blocks at once. Replacing enumeration with counting (a DP) and block-skipping (prefix sums) is the entire optimisation.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
x = 4Array state
counter
0,1,2,10 → indices 1,2,3,4
10C · Code with teaching comments
Reference implementation preview// Conceptual only — O(x) and infeasible for x up to 10^16. public String decibinaryNumbersBrute(long x) { long count = 0; for (long value = 0; ; value++) { for (String numeral : numeralsOf(value)) { // ascending; itself expensiveExplore the full codeHide the full code
D · Why it works and complexityO(x) per query — up to 10^16 timeO(1) or O(list) spaceOpen the invariant and proofExplore the proofHide the proof
We don't need the list, only counts and ranks. The moment you notice that 'how many numerals equal v?' is answerable without listing them, the O(x) walk collapses into a counting DP plus a prefix-sum jump.
ComplexityO(x) per query — up to 10^16 time, O(1) or O(list) space — Reaching index x requires producing on the order of x numerals; with x up to 10^16 and up to 10^5 queries, direct enumeration is astronomically too slow.
E · Edge cases and pitfalls3Believing it can pass — x up to 10^16 makes any per-numeral walk impossible.Explore edge casesHide edge cases
Pitfalls
- Believing it can pass — x up to 10^16 makes any per-numeral walk impossible.
- Generating numerals by brute digit enumeration — exponential per value.
- Re-walking from the start for every query instead of sharing work.
Approach 2 of 2 · Optimal
Counting DP + Prefix-Sum Ranking + Reconstruction (Optimal)
1Hint 1Explore hintHide hint
Phase 1 — count: count[b][v] = number of decibinary numerals using positions 0..b that evaluate to v. Choose digit a (0–9) for position b, contributing a·2^b, and recurse on the rest: sum count[b-1][v − a·2^b].
2Hint 2Explore hintHide hint
Phase 2 — locate: numWays[v] = count[topBit][v]; prefix-sum it. Binary search the smallest value d with prefix[d] ≥ x; then k = x − prefix[d-1] is the rank within value d.
3Hint 3Explore hintHide hint
Phase 3 — build: from the most-significant position down, try digits 0→9; pick the smallest digit whose number of completions (count of the remaining value over lower positions) is ≥ k, else subtract that count from k and try the next digit.
A · Core idea
Separate counting from ranking.
Phase 1 — the counting DP. Let count[b][v] be the number of decibinary numerals, using only positions 0..b, whose decimal value is exactly v. Base case count[0][v]: only position 0 (weight 1) is available, so the single digit must equal v — valid iff v ≤ 9, giving 1, else 0. Transition: at position b (weight 2^b) pick a digit a ∈ {0..9} with a·2^b ≤ v, then the remaining value v − a·2^b must be formed by lower positions: count[b][v] = Σ_a count[b-1][v − a·2^b]. Take BITS large enough that 2^(BITS-1) exceeds the largest value we need (positions above that are forced to digit 0). Then numWays[v] = count[BITS-1][v] is the total number of numerals equal to v.
Phase 2 — prefix sums and binary search. Build prefix[v] = Σ_{u≤v} numWays[u]. For a query x, the answer's decimal value is the smallest d with prefix[d] ≥ x (binary search, since prefix is non-decreasing). The rank of the answer within value d is k = x − prefix[d-1] (with prefix[-1] = 0).
Phase 3 — reconstruct the k-th numeral of value d. Build the numeral most-significant position first. At position p, try digits a = 0, 1, …: placing a uses a·2^p, leaving rem = remaining − a·2^p, which the lower positions 0..p-1 must form in waysBelow(p, rem) ways (that's count[p-1][rem], or 1/0 at the bottom). If k ≤ that count, fix digit a and move down a position; otherwise subtract the count from k and try a larger digit. Because we try digits in increasing order and fixed-width digit-string order equals numeral order (leading zeros don't change value), this lands exactly on the k-th smallest numeral. Strip leading zeros (value 0 prints as 0).
Why 64-bit. The cumulative count to cover x = 10^16 reaches ~10^16, and individual numWays/count values get into the trillions — well past 32-bit int but inside signed 64-bit long. Use long (Python ints are unbounded).
Why it's fast. Everything value-dependent is precomputed once. Each query is a binary search plus a ~20-position digit build, so 10^5 queries are trivial.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
x = 4 (numWays: [1,1,2,2,4,...]; prefix: [1,2,4,6,10,...])Array state
numWays
per-value counts
10C · Code with teaching comments
D · Why it works and complexityO(BITS·MAXV·10) precompute, O(log MAXV + BITS·10) per query timeO(BITS·MAXV) spaceOpen the invariant and proofExplore the proofHide the proof
The pivot is realising 'find the x-th numeral' = 'count buckets until you pass x, then index inside the bucket'. The counting DP fills the buckets, the prefix sum lets you skip whole buckets in one binary search, and the greedy digit build indexes within the bucket using the very same counts — three uses of one DP table.
ComplexityO(BITS·MAXV·10) precompute, O(log MAXV + BITS·10) per query time, O(BITS·MAXV) space — The DP fills BITS×(MAXV+1) cells, each summing ≤ 10 terms → O(BITS·MAXV·10) one-time. Prefix sums are O(MAXV). Each query does a binary search O(log MAXV) and a digit build over BITS positions × ≤ 10 digit trials → O(BITS·10). MAXV ≈ 285k and BITS ≈ 20.
E · Edge cases and pitfalls8x = 1 — Binary search → d = 0 (prefix[0] = 1 ≥ 1), k = 1; reconstruction yields all-zero digits → printed as '0'.Explore edge casesHide edge cases
Edge cases handled
x = 1Binary search → d = 0 (prefix[0] = 1 ≥ 1), k = 1; reconstruction yields all-zero digits → printed as '0'.x = 10prefix[3] = 6 < 10 ≤ prefix[4] = 10 → d = 4, k = 4 → '100' (the 4th numeral of value 4).x at a block boundaryIf prefix[d] == x exactly, k equals numWays[d] → the LAST (largest) numeral of value d.very large x near 10^16d lands near MAXV; counts stay within 64-bit, so longs hold them correctly.
Pitfalls
- Using int for count/prefix — overflows around 2·10^9 while real values reach ~10^16.
- Choosing MAXV/BITS too small so prefix never reaches 10^16 (out-of-range queries) — size them to the constraints.
- Reconstructing least-significant-first or trying digits 9→0 — yields the wrong rank ordering.
- Off-by-one in k: it's x − prefix[d-1], 1-based within the block, not x − prefix[d].
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewimport java.util.*; public class Decibinary { static final int BITS = 20; // 2^19 > MAXV, so higher positions are forced to 0 static final int MAXV = 285115; // cumulative count exceeds 10^16 within this rangeExplore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Integer overflow on the counts
The per-value counts and prefix sums climb into the trillions and beyond (x can be 10^16). A 32-bit int wraps around silently, corrupting both the binary search and the reconstruction.
Explore the code comparisonHide the code comparison
Integer overflow on the counts
The per-value counts and prefix sums climb into the trillions and beyond (x can be 10^16). A 32-bit int wraps around silently, corrupting both the binary search and the reconstruction.
Don't write this
int[][] count = new int[BITS][MAXV + 1]; // overflows; counts exceed 2^31Write this instead
long[][] count = new long[BITS][MAXV + 1]; // counts approach 10^16 → 64-bit2Reconstructing digits in the wrong order
Numeral order equals fixed-width digit-string order only when you fix the MOST-significant position first and try digits 0→9. Building least-significant-first, or trying 9→0, returns a different (wrong) numeral for the same rank.
Explore the code comparisonHide the code comparison
Reconstructing digits in the wrong order
Numeral order equals fixed-width digit-string order only when you fix the MOST-significant position first and try digits 0→9. Building least-significant-first, or trying 9→0, returns a different (wrong) numeral for the same rank.
Don't write this
for p in range(BITS): # least-significant first → wrong ordering
for a in range(9, -1, -1): # largest digit first → wrong ordering
...Write this instead
for p in range(BITS - 1, -1, -1): # most-significant first
a = 0
while a <= 9 and a * (1 << p) <= remaining: # smallest digit first
...3Recomputing per query instead of precomputing
The counting DP and prefix sums depend only on the value range, not on x. Rebuilding them inside each of up to 10^5 queries multiplies an O(BITS·MAXV) cost by the query count and times out.
Explore the code comparisonHide the code comparison
Recomputing per query instead of precomputing
The counting DP and prefix sums depend only on the value range, not on x. Rebuilding them inside each of up to 10^5 queries multiplies an O(BITS·MAXV) cost by the query count and times out.
Don't write this
def answer(x):
build_dp() # O(BITS*MAXV) every call — too slow
...Write this instead
build_dp() # once, at startup
def answer(x):
... # O(log MAXV + BITS) per queryRevise
Carry the pattern into the interview
Pattern to remember
Counting DP + prefix-sum index lookup + greedy digit reconstruction (a digit-DP)
Code pattern to memorize
count[b][v] = Σ_{a=0..9, a·2^b ≤ v} count[b-1][v − a·2^b] (base: count[0][v] = 1 if v ≤ 9 else 0)
numWays[v] = count[BITS-1][v] # numerals equal to v
prefix[v] = Σ_{u≤v} numWays[u]
# query x: d = smallest value with prefix[d] ≥ x; k = x − prefix[d-1]
# reconstruct k-th smallest numeral of value d, MSB→LSB, smallest digit firstRules to remember
- 1Decibinary value = Σ digit·2^position, but digits range 0–9 (not 0–1) — that's why many numerals share one value.
- 2The global list is ordered by (decimal value asc, then numeral asc); index 1 is the numeral
0(value 0). - 3Counts get huge — up to ~10^16 — so accumulate in 64-bit (
long); 32-bitintoverflows silently. - 4Reconstruct from the most-significant position downward, trying digits 0→9; the smallest digit that still leaves ≥ k completions is the one to fix (fixed-width digit order = numeral order).
- 5Precompute the DP and prefix sums once; each of the up-to-10^5 queries is then a binary search plus a short digit build.
Use this pattern when
- Count representations / objects bucketed by some value, then index the k-th by rank
- A 'find the x-th in sorted order' query answered without materialising the list
- Digit-by-digit construction where each prefix's completion count is computable
- Positional/place-value counting with bounded digits (digit DP)
Choose another pattern when
- Only a yes/no or a single total is needed → the count DP alone suffices, skip reconstruction
- Values/queries are tiny → brute enumeration is simpler and fine
- Digits are unbounded or the value range is astronomical → can't tabulate; need a smarter closed form
- Order is by something other than value-then-numeral → re-derive the ranking
Interview takeaway
Two classic ideas compose here: a counting DP that tells you how many things land in each bucket, and prefix-sums + greedy reconstruction that turn those counts into the k-th element by rank — the standard recipe for 'find the x-th ... in sorted order' problems.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternCounting DP + prefix-sum ranking + greedy reconstruction is the canonical recipe for 'find the x-th object in sorted order' when the objects are far too many to list. Count how many fall in each bucket, prefix-sum to jump to the right bucket, then reconstruct within it using the same counts. Same skeleton as Permutation Sequence and K-th Smallest in Lexicographical Order.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Count decibinary numerals equal to vJust phase 1 — the counting DP's top row numWays[v], without ranking.
- Number of Digit OneComing soonAnother digit-DP / place-value counting problem — count a property across numbers.
- Permutation SequenceComing soonSame 'k-th in sorted order via factorial counts + greedy reconstruction' recipe.
- K-th Smallest in Lexicographical OrderComing soonCount subtree sizes, skip blocks, descend — the ranking pattern again.