Numbers Without d as Digit

Problem Overview

Count integers in 1..n whose decimal form never uses digit d.

Intuition

Count integers in 1..n whose decimal form never uses digit d. Brute force over n is too slow when n is large, so build the answer digit by digit (digit DP). States remember the position, whether we are still glued to the upper bound n (tight), and whether we have started the number yet so leading zeros are not treated as forbidden digit d until a real digit is placed.

Algorithm

1If n == 0 return 0. Convert n to a digit string and clear a memo[pos][tight][started].
2DFS(pos, tight, started): if pos reaches the end, return 1 if started else 0.
3Limit the current digit to digits[pos] when tight, else 9.
4For each digit 0..limit: if not started and digit is 0, continue with started=false (leading zero). Else if digit != d, continue with started=true.
5Memoize and return the count.

Example Walkthrough

Input: n = 13, d = 1

1. Valid numbers in 1..13 with no digit 1: 2,3,4,5,6,7,8,9.
2. 10,11,12,13 each contain digit 1 and are skipped.
3. Answer is 8.

Output: 8

Common Pitfalls

• Leading zeros must not count as using digit d - keep a started flag.
• Reset memo for every query; states depend on the digit string of n.
• When digit == d and the number has started, skip that branch entirely.
• n == 0 is an empty range - return 0, not 1.

Numbers Without d as Digit.java

Java

// Approach: Digit DP over the decimal representation of n. At each position
// track (pos, tight, started): whether we still match the prefix of n, and
// whether we have placed a non-leading zero. Skip choosing digit d once the
// number has started; leading zeros are allowed and do not count as using d
// until the number actually starts. Memoize states.
// Complexity: O(log n) time and O(log n) space (digit length is O(log n)).

class Solution {

    private Integer[][][] memo;

    public int countWithout(int n, int d) {
        if (n == 0) {
            return 0;
        }

        String digits = String.valueOf(n);
        int len = digits.length();
        memo = new Integer[len][2][2];

        return countDigitFree(0, true, false, digits, d);
    }

    private int countDigitFree(int pos, boolean tight, boolean started, String digits, int d) {
        if (pos == digits.length()) {
            return started ? 1 : 0;
        }

        int tightIdx = tight ? 1 : 0;
        int startedIdx = started ? 1 : 0;

        if (memo[pos][tightIdx][startedIdx] != null) {
            return memo[pos][tightIdx][startedIdx];
        }

        int limit = tight ? (digits.charAt(pos) - '0') : 9;
        int count = 0;

        for (int digit = 0; digit <= limit; digit++) {
            boolean newTight = tight && (digit == limit);

            if (!started && digit == 0) {
                count += countDigitFree(pos + 1, newTight, false, digits, d);
            } else if (digit != d) {
                count += countDigitFree(pos + 1, newTight, true, digits, d);
            }
        }

        return memo[pos][tightIdx][startedIdx] = count;
    }
}

Was this solution helpful?