Count Special Integers

The problem is to count special numbers up to n. This can be solved using digit dynamic programming and combinatorics. Let S be the string representation of n and L be its length.

The count is divided into two parts:

1. Count special numbers with fewer digits than n:

   • Iterate for each length d from 1 to L-1.
   • For a d-digit number, the first digit has 9 choices (1-9). The remaining d-1 digits are a permutation of d-1 digits chosen from the 9 remaining available digits (0-9 excluding the first digit).
   • The count for length d is 9 * P(9, d-1), where P(m, k) is the number of k-permutations of m.
   • Sum these counts for all d < L.

2. Count special numbers with the same number of digits as n and are less than or equal to n:

   • Iterate through the digits of n from left to right (index i from 0 to L-1).
   • Maintain a set of digits seen in the prefix.
   • At each position i, consider placing a digit d that is smaller than the digit n[i].
   • For each such valid d (not 0 for the first position and not in seen), the remaining L-1-i positions can be filled in P(10 - (i+1), L-1-i) ways. Add this to the total count.
   • After checking smaller digits, check the digit n[i] itself. If n[i] is already in seen, it means n and any other number with this prefix is not special. We must stop and return the current count.
   • If n[i] is not in seen, add it to seen and proceed to the next position i+1.

3. Final check for n:

   • If the loop completes, it means n itself is a special number. Increment the final count by 1.

Let's illustrate with n = 135. The string is S = "135" and length L = 3.

Part 1: Count special numbers with length < 3

• 1-digit numbers: 9 (1-9).
• 2-digit numbers: The first digit has 9 choices (1-9). The second has 9 choices (0-9, excluding the first). Total: 9 * 9 = 81.
• Total for length < 3: 9 + 81 = 90.

Part 2: Count 3-digit special numbers <= 135

• We iterate through S = "135".
• Position 0 (hundreds): S[0] = '1'. We can't place a smaller digit (since it would have to be 0, which is not allowed as the first digit). So we must place '1'. Mark '1' as seen.
• Position 1 (tens): S[1] = '3'. We can place digits smaller than 3.
  • Try d = 0: '0' is not seen. We form 10_. The last digit has 8 choices (0-9, excluding 1 and 0). Add 8 to count.
  • Try d = 2: '2' is not seen. We form 12_. The last digit has 8 choices. Add 8 to count.
  • Now, we must place '3'. Mark '3' as seen.
• Position 2 (ones): S[2] = '5'. We can place digits smaller than 5.
  • Try d = 0, 2, 4 (1 and 3 are seen). For each, we form 130, 132, 134. These are 3 numbers. Add 3 to count.
• The loop finishes. Since 135 itself has distinct digits, we add 1 for it.
• Total for 3-digit numbers: 8 + 8 + 3 + 1 = 20.

Grand Total: 90 + 20 = 110.

Here is the code for this approach:

1class Solution {2    public int countSpecialNumbers(int n) {3        String s = String.valueOf(n);4        int L = s.length();5        int res = 0;6 7        // Count special numbers with length < L8        for (int d = 1; d < L; d++) {9            res += 9 * permutations(9, d - 1);10        }11 12        // Count special numbers with length L and <= n13        boolean[] seen = new boolean[10];14        for (int i = 0; i < L; i++) {15            int digit = s.charAt(i) - '0';16            for (int d = (i == 0) ? 1 : 0; d < digit; d++) {17                if (!seen[d]) {18                    res += permutations(10 - (i + 1), L - 1 - i);19                }20            }21            if (seen[digit]) {22                return res; // Duplicate digit found in n's prefix23            }24            seen[digit] = true;25        }26 27        // If we reach here, n itself is a special number28        res++;29        return res;30    }31 32    // Calculates P(m, n) = m! / (m-n)!33    private int permutations(int m, int n) {34        if (n > m) return 0;35        int res = 1;36        for (int i = 0; i < n; i++) {37            res *= (m - i);38        }39        return res;40    }41}