Numbers At Most N Given Digit Set

Numbers At Most N Given Digit Set

What is this problem about?

The Numbers At Most N Given Digit Set problem gives you a sorted set of digits D and a number N. Count how many positive integers ≤ N can be formed using only digits from D (with repetition allowed). This hard coding problem uses digit DP combined with combinatorial prefix counting.

Why is this asked in interviews?

Microsoft, Amazon, and TikTok ask this because it requires combining digit-by-digit constraint checking with the counting of "all shorter numbers" using powers of |D|. The array, math, binary search, string, and dynamic programming interview pattern is the core.

Algorithmic pattern used

Digit DP + prefix counting. Let N have L digits. Count in two parts: (1) all valid numbers with fewer than L digits: |D|^1 + |D|^2 + ... + |D|^(L-1). (2) Numbers with exactly L digits: digit-by-digit, for each position, count choices strictly less than N's digit, then multiply by |D|^(remaining positions). If exact match possible (digit is in D), continue; otherwise stop.

Example explanation

D=["1","3","5","7"], N=100. L=3. Part 1: |D|^1 + |D|^2 = 4+16 = 20 (1-digit and 2-digit numbers). Part 2: L=3 digit numbers.

• Position 0: digits in D less than '1': none (0 choices × 4^2). Digit '1' in D? No ('1' is in D). Continue. Wait D has '1' so: digit N[0]='1'. Choices < '1' in D: none. '1' in D → continue.
• Position 1: N[1]='0'. Digits in D < '0': none. '0' not in D → stop. Part 2 contribution = 0. Total = 20. Answer = 20.

Common mistakes candidates make

• Not handling numbers shorter than N separately.
• Off-by-one in power computation.
• Missing the "exact match" continuation when a digit equals N's digit.
• Not using binary search to check if a digit is in D.

Interview preparation tip

"Count numbers with restricted digits ≤ N" always has two components: shorter numbers (|D|^1 + ... + |D|^(L-1)) and same-length numbers (digit-by-digit counting). The digit-by-digit pass checks: choices-less-than × |D|^remaining + (if digit in D: continue else stop). Practice this digit counting technique — it appears in many "count numbers satisfying property ≤ N" problems.