1012. Numbers With Repeated Digits (Hard)

Given an integer n, return the number of positive integers in the range [1, n] that have at least one repeated digit.

 

Example 1:

Input: n = 20
Output: 1
Explanation: The only positive number (<= 20) with at least 1 repeated digit is 11.

Example 2:

Input: n = 100
Output: 10
Explanation: The positive numbers (<= 100) with atleast 1 repeated digit are 11, 22, 33, 44, 55, 66, 77, 88, 99, and 100.

Example 3:

Input: n = 1000
Output: 262

 

Constraints:

• 1 <= n <= 109

Companies:
Akuna Capital, IBM, Google

Related Topics:
Math, Dynamic Programming

Solution 1. Bitmask DP

Let's say a good number is a number without repeated digits.

This problem is the same as counting good numbers in [1,n].

Firstly, express n as an digits array. Example: n = 2345, digits = [2,3,4,5].

Let f[mask][i] be the count of good numbers whose j >= ith digit is <= digits[j] and is not selected in mask. The answer is n - f[0][0].

Example:

Assume digits = [2,3,4,5], if we select 2 as the first digit, then we go from state f[0][0] to f[100][1] where f[100][1] is the count of good numbers whose j >= 1th digit is <= digits[j] and is not 2 (because mask = 100).

For f[mask][i], we can try all digits d that are <= digits[i] and don't conflict with mask.

If we selects a digit d that is < digit[i], then the following digits are not confined by digits but only by mask.

Let g[mask][len] be the count of good numbers of length len those digits don't conflict with mask.

For g[mask][len], we can try all digits d that don't conflict with mask:

g[mask][len] = SUM( g[newMask, len - 1] | 0 <= d <= 9 && d is not conflict with mask )
                where newMask = d == 0 && mask == 0 ? 0 : (1 << d | mask)

f[mask][i] = SUM( g[newMask][digits.size() - 1 - i] | 0 <= d < digits[i] && d is not conflict with mask )
                where newMask = d == 0 && mask == 0 ? 0 : (1 << d | mask)
              + ((mask >> digits[i] & 1) == 0 ? f[1 << digit[i] | mask][i+1] : 0)

// OJ: https://leetcode.com/problems/numbers-with-repeated-digits/
// Author: github.com/lzl124631x
// Time: O(2^lgN * lgN)
// Space: O(2^lgN * lgN)
class Solution {
public:
    int numDupDigitsAtMostN(int n) {
        vector<int> digits;
        for (int m = n; m; m /= 10) digits.push_back(m % 10);
        reverse(begin(digits), end(digits));
        int mg[1024][10] = {};
        memset(mg, -1, sizeof(mg));
        function<int(int, int)> g = [&](int mask, int len) -> int {
            if (len == 0) return mask != 0;
            if (mg[mask][len] != -1) return mg[mask][len];
            int ans = 0;
            for (int d = 0; d <= 9; ++d) {
                if (mask >> d & 1) continue;
                int newMask = d == 0 && mask == 0 ? 0 : (1 << d | mask);
                ans += g(newMask, len - 1);
            }
            return mg[mask][len] = ans;
        };
        function<int(int, int)> f = [&](int mask, int i) {
            if (i == digits.size()) return 1;
            int ans = 0;
            for (int d = 0; d < digits[i]; ++d) {
                if (mask >> d & 1) continue;
                int newMask = d == 0 && mask == 0 ? 0 : (1 << d | mask);
                ans += g(newMask, digits.size() - 1 - i);
            }
            if ((mask >> digits[i] & 1) == 0) ans += f(1 << digits[i] | mask, i + 1);
            return ans;
        };
        return n - f(0, 0);
    }
};

TODO

Read https://leetcode.com/problems/numbers-with-repeated-digits/discuss/?currentPage=1&orderBy=most_votes&query=