Skip to content

1012. Numbers With Repeated Digits 👍

Approach 1: DFS

  • Time: $O((\log n)!)$
  • Space: $O((\log n)!)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
 public:
  int numDupDigitsAtMostN(int N) {
    int uniqueNumbers = 0;
    dfs(N, 0, 0, uniqueNumbers);
    return N - uniqueNumbers + 1;
  }

 private:
  void dfs(int N, int mask, long path, int& uniqueNumbers) {
    if (path > N)
      return;

    ++uniqueNumbers;

    for (int digit = 0; digit < 10; ++digit) {
      if (mask == 0 && digit == 0)
        continue;
      if (mask & 1 << digit)
        continue;
      dfs(N, mask | 1 << digit, path * 10 + digit, uniqueNumbers);
    }
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
  public int numDupDigitsAtMostN(int N) {
    dfs(N, 0, 0);
    return N - uniqueNumbers + 1;
  }

  private int uniqueNumbers = 0;

  private void dfs(int N, int mask, long path) {
    if (path > N)
      return;

    ++uniqueNumbers;

    for (int digit = 0; digit < 10; ++digit) {
      if (mask == 0 && digit == 0)
        continue;
      if ((mask & 1 << digit) > 0)
        continue;
      dfs(N, mask | 1 << digit, path * 10 + digit);
    }
  }
}

Approach 2: Count

  • Time: $O(\log n)$
  • Space: $O(\log n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
 public:
  int numDupDigitsAtMostN(int N) {
    int uniqueNumbers = 0;
    vector<int> digits;  // N + 1
    unordered_set<int> seen;

    // transfer N + 1 to an array of digits
    for (int i = N + 1; i > 0; i /= 10)
      digits.push_back(i % 10);
    reverse(begin(digits), end(digits));

    const int n = digits.size();

    // unique numbers w/ digits < n
    for (int i = 1; i < n; ++i)
      uniqueNumbers += 9 * P(9, i - 1);

    // unique numbers w/ digits = n and same prefix
    for (int i = 0; i < n; ++i) {
      for (int j = i > 0 ? 0 : 1; j < digits[i]; ++j)
        if (!seen.count(j))
          uniqueNumbers += P(9 - i, n - i - 1);
      if (seen.count(digits[i]))
        break;
      seen.insert(digits[i]);
    }

    return N - uniqueNumbers;
  }

 private:
  int P(int m, int n) {
    int ans = 1;
    for (int i = m - n + 1; i <= m; ++i)
      ans *= i;
    return ans;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public class Solution {
  public int numDupDigitsAtMostN(int N) {
    int uniqueNumbers = 0;
    List<Integer> digits = new ArrayList<>(); // N + 1
    Set<Integer> seen = new HashSet<>();

    // transfer N + 1 to an array of digits
    for (int i = N + 1; i > 0; i /= 10)
      digits.add(i % 10);
    Collections.reverse(digits);

    final int n = digits.size();

    // unique numbers w/ digits < n
    for (int i = 1; i < n; ++i)
      uniqueNumbers += 9 * P(9, i - 1);

    // unique numbers w/ digits = n and same prefix
    for (int i = 0; i < n; ++i) {
      for (int j = i > 0 ? 0 : 1; j < digits.get(i); ++j)
        if (!seen.contains(j))
          uniqueNumbers += P(9 - i, n - i - 1);
      if (seen.contains(digits.get(i)))
        break;
      seen.add(digits.get(i));
    }

    return N - uniqueNumbers;
  }

  private int P(int m, int n) {
    int ans = 1;
    for (int i = m - n + 1; i <= m; ++i)
      ans *= i;
    return ans;
  }
}
Back to top