Count Numbers Containing Specific Digits

JavaView on GFG

Intuition

Count numbers in range [1, n] that contain at least one of the given specific digits.

Algorithm

1Digit DP: count numbers with all digits NOT in the set, subtract from total n.

Common Pitfalls

•Complement counting is easier. Count numbers with no forbidden digits using digit DP or combinatorics.

Count Numbers Containing Specific Digits.java

Java

// Approach: Digit DP or direct enumeration. Count numbers in range containing all specified digits.
// Time: O(log n) Space: O(1)
import java.util.*;

class Solution {
    public int countValid(int n, int[] arr) {
        if (n == 1) {
            Arrays.sort(arr);
            if (arr[0] == 0)
                return arr.length - 1;
            else
                return arr.length;
        }
        long totalNumbers = 9; // Use long to prevent overflow for larger n
        for (int i = 0; i < n - 1; i++)
            totalNumbers *= 10;

        Set<Integer> arrSet = new HashSet<>();
        for (int digit : arr)
            arrSet.add(digit);

        int numUnavailableDigits = arr.length;
        int numAvailableNonArrDigits = 10 - numUnavailableDigits;

        long numbersWithoutArrDigits = 1;

        int firstDigitChoices = 0;
        for (int i = 1; i <= 9; i++) { // Iterate through 1-9
            if (!arrSet.contains(i))
                firstDigitChoices++;
        }
        numbersWithoutArrDigits = firstDigitChoices;

        for (int i = 0; i < n - 1; i++)
            numbersWithoutArrDigits *= numAvailableNonArrDigits;

        return (int) (totalNumbers - numbersWithoutArrDigits);
    }
}

Was this solution helpful?