O(1) / O(1) via precomputation
IntuitionThere are far more numbers that have repeated digits than those that don't. If we can efficiently enumerate all the numbers that do not have repeated d
# Intuition
There are far more numbers that have repeated digits than those that don't. If we can efficiently enumerate all the numbers that do not have repeated digits into a sorted array, then we can use a binary search to efficiently count the number that are less than `n+1`. Subtracting that from `n` will give us the count of numbers that do have repeated digits.

# Approach
Precompute all numbers that have no repeated digits and sort them when the program starts. Run a binary search for each individual query.

To save time we can do a couple simple things:
1. Precompute the values in order, so they don't have to be sorted.
2. Preallocate the array, since the number of elements is fixed at 8,877,690.

Also to save time, we want to already know which digits are unused in each value when we reach it. This allows us to save time by iterating over just the unused digits instead of over all 10 digits. Attempting to use a second array for this will run us out of memory, so we get a bit clever.
1. When we first add a value to the array we left shift it by 10 bits and also store a bit set representing the digits that are not part of that number.
2. Later when when we reach each value, we first extract the set of unused digits and then right shift the element to restore the original value.

This is not a fantastically intuitive approach, but it cuts the precomputation time significantly. In Go, this allows the entire bad array to be created in less than 50 milliseconds.

# Complexity
- Time complexity: $$O(1)$$
Binary search runs in $$O(log(len(array)))$$. The array's size is fixed, regardless of the value of `n`.
Since the base is fixed to 10, precomputation of the array is also $$O(1)$$.
If the base, `b`, were not fixed, the precomputation time would be dominated by the permuation of all `b` digits, which would take $$O(b!)$$ time.

- Space complexity: $$O(1)$$
Precomputation creates an array of fixed size for a fixed base. Therefore space is $$O(1)$$.
If the base, `b`, were not fixed, the precomputed array's contents would be dominated by the permuation of all `b` digits, which would take $$O(b!)$$ space.


# Code
```golang []
// Preallocating space drops the time for init() significantly
var bad = make([]int, 0, 8_877_690)

func init() {

    // Bit set of all 10 digits
    var full int = 1 << 10 - 1

    for i := 1; i < 10; i++ {
        // Make bit set of digits other than i
        mask := full &^ (1 << i)
        // Add both the value and the bit set to the array
        bad = append(bad, i << 10 | mask)
    }

    for i := 0; i < len(bad); i++ {

        // Extract the set of unused digits
        open := bad[i] & full
        // Make the element just the value
        bad[i] >>= 10

        for curr, b := open, 0; curr > 0; curr ^= b {
            // Get the LSB from those remaining
            b = curr & -curr
            // Convert that bit to the digit it represents
            d := bits.Len(uint(b)) - 1
            // Get the correct mask for the next value
            mask := open ^ (1 << d)
            // Add the next value and its mask to the array
            bad = append(bad, (10*bad[i]+d) << 10 | mask)
        }

    }

}

func numDupDigitsAtMostN(n int) int {
    // Binary search for n+1 in case n is in the array
    return n - sort.SearchInts(bad, n+1)
}
```
['Go']