Leetcode 1012. Numbers With Repeated Digits

Problem

This problem requires you to create a function that takes in a positive integer N, and returns the number of positive integers less than or equal to N that have at least 1 repeated digit.

For example, given the input 20, your function should return 1, because the only number with a repeated digit less than or equal to 20 is 11. Given the input 100, your function should return 10, because the numbers with repeated digits less than or equal to 100 are: 11, 22, 33, 44, 55, 66, 77, 88, 99, and 100.

Approach

The solution approach utilizes dynamic programming by keeping track of numbers with unique digits and calculating those with repeated digits indirectly by subtracting the unique-digit numbers from the total. As we traverse over the digits of the input, we store the solution of the problem for each digit position with the help of a 3D dp array.

Algorithm and Examples

To illustrate, let's say the input number is 100.

  1. We start by calculating the number of unique digit numbers less than 100.
  2. We iterate over each digit from the left, and for each digit, we have two cases: the current digit is less than the current digit in N or equal to the current digit in N.
  3. For each case, if the current number is less than N, we find out all the ways we can fill in the remaining digits. Add this to the current count of unique numbers.
  4. If the current digit is greater than N, we can't process further and continue with the next digit.
  5. We continue processing the digits to the right until we've processed all digits in N.
  6. Once we've done all this, we subtract the count of unique digits numbers from N to get the number of numbers with duplicated digits.

Let's walk through an example with inputs n = 20.

  • First, we compute the size of the number by applying log10 to n. So, log10(20) is around 2. We add 1 to include all digits in further calculations.
  • We initialize a 3-dimensional array, dp, of size (digitSize+1) x (1<<10) x 2. The dp array stores the count of unique digits for each digit.
  • Now we start the count function with the current index as 0, usedMask as 0, and isTight as True.
  • In the count function, if the current index is equal to the length of the number, we return 1 as we have a unique digit number.
  • If we have calculated the count for the current state, we return the computed value.
  • Now, we store the maximum digit we can append to the current number. If the number is less than the input number (isTight is false), the maximum digit is 9 otherwise it's equal to the current digit in N.
  • Now we iterate over the digits from 0 to maxDigit and calculate the count of unique returns.
  • Then we continue the process for the next digit in N.
  • Lastly, the total count for the current state is stored in dp and returned.
  • The difference between the input number and the count of special numbers gives the numbers with repeated digits.

Solution

Python

1
2python
3class Solution:
4    def numDupDigitsAtMostN(self, N: int) -> int:
5        digits = list(map(int, str(N+1)))
6        n = len(digits)
7
8        def count(bound, idx, pre, mask, limit):
9            if idx == n:
10                return 1
11            if pre and dp[idx][mask] != -1:
12                return dp[idx][mask]
13            maxval = digits[idx] if bound else 9
14            res = 0
15            for i in range(maxval+1):
16                if (mask >> i) & 1:
17                    continue
18                res += count(bound & (i == maxval), idx+1, pre & (i == 0), mask | (1 << i), limit)
19            if pre:
20                dp[idx][mask] = res
21            return res
22
23        dp = [[-1] * (1 << 10) for _ in range(10)]
24        return N+1 - count(True, 0, True, 0, n)

Java

1
2java
3class Solution {
4    int[] num;
5    boolean[] vis;
6    int[][] dp;
7    
8    public int numDupDigitsAtMostN(int N) {
9        num = new int[11];
10        vis = new boolean[11];
11        dp = new int[11][11];
12        int cnt=0;
13        for(int i=N+1;i>0;i/=10)num[++cnt]=i%10;
14        int ans=count(cnt,0,false,true)-1;
15        return N-ans;
16    }
17    
18    private int count(int pos,int sta,boolean lead,boolean limit){
19        if(pos==0)return 1;
20        if(!limit && !lead && dp[pos][sta]!=0)return dp[pos][sta];
21        int up=limit? num[pos]:9;
22        int tmp=0;
23        for(int i=0;i<=up;i++){
24            if((sta&(1<<i))>0)continue;
25            if(i==0 && lead)tmp+=count(pos-1,sta,true,limit && i==num[pos]);
26            else tmp+=count(pos-1,sta|(1<<i),false,limit && i==num[pos]);
27        }
28        if(!limit && !lead)
29            dp[pos][sta]=tmp;
30        return tmp;
31    }
32}

C++

1
2c++
3class Solution {
4public:
5    int numDupDigitsAtMostN(int n) {
6        return n - countSpecialNumbers(n);
7    }
8
9private:
10  int countSpecialNumbers(int n) {
11    const int digitSize = log10(n) + 1;
12    dp.resize(digitSize + 1, vector<vector<int>>(1 << 10, vector<int>(2, -1)));
13    return count(to_string(n), 0, 0, true) - 1; 
14  }
15
16private:
17  vector<vector<vector<int>>> dp;
18
19  int count(const string& s, int i, int usedMask, bool isTight) {
20    if (i == s.length())
21      return 1;
22    if (dp[i][usedMask][isTight] != -1)
23      return dp[i][usedMask][isTight];
24
25    int res = 0;
26    const int maxDigit = isTight ? s[i] - '0' : 9;
27
28    for(int d=0; d<=maxDigit; d++){
29      if(usedMask >> d & 1)
30        continue;
31      bool nextIsTight = isTight && (d == maxDigit);
32      if(usedMask==0 && d==0) 
33        res += count(s, i + 1, usedMask, nextIsTight);
34      else
35        res += count(s, i + 1, usedMask|1 << d, nextIsTight);
36    }
37    return dp[i][usedMask][isTight] = res;
38  }
39};

C#

1
2csharp
3public class Solution {
4    public int NumDupDigitsAtMostN(int N) {
5        int[] num = new int[11], dp = new int[11];
6        bool[] vis = new bool[11];
7        int cnt = 0;
8        for (int i = N + 1; i > 0; i /= 10) num[++cnt] = i % 10;
9        int ans = Count(num, cnt, 0, true, true, vis, dp) - 1;
10        return N - ans;
11    }
12    
13    private int Count(int[] num, int pos, int sta, bool lead, bool limit, bool[] vis, int[] dp) {
14        if(pos == 0) return 1;
15        if (!limit && !lead && dp[pos] > 0) return dp[pos];
16        int up = limit ? num[pos] : 9;
17        int tmp = 0;
18        for (int i = 0; i <= up; i++) {
19            if((sta & (1 << i)) > 0) continue;
20            if (i == 0 && lead) {
21                tmp+=Count(num, pos - 1, sta, true, limit && i == num[pos], vis, dp);
22            } else {
23                vis[i] = true;
24                tmp += Count(num, pos - 1, sta | (1 << i), false, limit && i == num[pos], vis, dp);
25                vis[i] = false;
26            }
27        }
28        if (!limit && !lead) dp[pos] = tmp;
29        return tmp;
30    }
31}

Please note that the code above uses dp for memoization.### JavaScript

In JavaScript, the solution that leverages recursion and memoization can be implemented in the following way:

1
2javascript
3var numDupDigitsAtMostN = function(N) {
4    let num = [];
5    let dp = Array(25).fill(0).map(_ => Array(1 << 10).fill(0).map(_ => Array(2).fill(0)));
6    for(let i = N + 1; i > 0; i = Math.floor(i / 10)) num.push(i % 10);
7    num = num.reverse();
8    return N + 1 - solve(dp, num, 0, 0, true);
9};
10
11function solve(dp, num, index, state, limit) {
12    if(index == num.length) return 1;
13    if(!limit && dp[index][state]) return dp[index][state];
14    let max = limit ? num[index] : 9;
15    let ans = 0;
16    for(let i = 0; i <= max; i++) {
17        if((state >> i) & 1) continue;
18        ans += solve(
19            dp, num, index + 1, 
20            i == 0 && state == 0 ? 0 : (state | (1 << i)), 
21            limit && i == max);
22    }
23    if(!limit) dp[index][state] = ans;
24    return ans;
25}

In the JavaScript solution, we use a similar logic to the one followed in other languages. We represent the number as an array of digits. In addition, we also use a 3D dp array for storing intermediate results of our recursion and applying memoization. The solve function implements the main logic, iterating over possible next digits and summing up the results of recursive calls, and the final result for input N is computed by subtracting the return value of solve from N+1, because we want to find out the numbers with repeated digits. This solution is optimized enough to pass for inputs as large as 10^9 within reasonable time.

Conclusion

In this problem, we have to find the numbers with repeated digits for given N. The approach involves counting numbers with unique digits (which we termed as "special numbers") and subtracting them from N to get the numbers with repeated digits. This requires a clear understanding of dynamic programming, and we need to handle several edge cases carefully to make sure our algorithm works correctly. Considering these features can be quite important when solving similar problems in competitive programming or interview scenarios. Being familiar with techniques such as dynamic programming and recursion can enable us to come up with an efficient solution for this problem.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫