Numbers With Repeated Digits

Numbers With Repeated Digits

What is this problem about?

The Numbers With Repeated Digits problem asks you to count integers from 1 to N that have at least one repeated digit. Using complementary counting — total numbers minus numbers with all distinct digits — the problem reduces to counting distinct-digit numbers ≤ N. This hard coding problem uses digit DP with a permutation counting approach.

Why is this asked in interviews?

J.P. Morgan, Goldman Sachs, Microsoft, and Google ask this because the complementary counting approach plus digit-by-digit permutation analysis is elegant and non-trivial. The math and dynamic programming interview pattern is demonstrated through careful digit enumeration with permutation formulas.

Algorithmic pattern used

Complementary counting + digit DP. Count distinct-digit numbers ≤ N. For numbers shorter than N's length: sum of 9 * P(9, k-1) for k=1..L-1 (choosing k digits with first non-zero). For same-length: digit-by-digit, track used digits. At each position, count choices (digits not yet used that are less than N's current digit), multiply by permutations of remaining positions. Answer = N - distinct_count.

Example explanation

N=20. L=2. Shorter (1-digit): 1..9 → 9 numbers with distinct digits. Same-length (2-digit): first digit choices from {1-9} < '2': {1}. Count=1. Remaining 1 position: 9 choices (any digit ≠ 1). 9 numbers. Plus: first digit = '2', second < '0': none. Result: 9+9=18... Actually 9 + (second digit for 1X: any of 9 excluding 1) = 9. Total distinct ≤ 20: 9+1*(9)... let me simplify: distinct-digit count = 9+9+1=19 (1-9, 10-19 excluding 11, 20). Repeated = 20-19=1 (only 11).

Common mistakes candidates make

• Computing repeated digits directly (much harder than complementary counting).
• Off-by-one in permutation formula: P(n,k) = n!/(n-k)!.
• Not handling numbers with leading zeros correctly.
• Missing the "same length, digit exactly matching" continuation.

Interview preparation tip

"Count numbers with repeated digits" is best solved as N - count(distinct-digit numbers ≤ N). Counting distinct-digit numbers uses the permutation formula: P(9,k-1) for numbers with k digits (first digit from 1-9, remaining from all unused). Digit-by-digit for same-length numbers tracks which digits are used. Practice complementary counting on digit problems — it's often simpler than direct counting.