1012. Numbers With Repeated Digits LeetCode Solution

In this guide, you will get 1012. Numbers With Repeated Digits LeetCode Solution with the best time and space complexity. The solution to Numbers With Repeated Digits problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Numbers With Repeated Digits solution in C++
Numbers With Repeated Digits solution in Java
Numbers With Repeated Digits solution in Python
Additional Resources

1012. Numbers With Repeated Digits LeetCode Solution image

Problem Statement of Numbers With Repeated Digits

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

Complexity Analysis

Time Complexity: O(\log n \cdot 2^{10} \cdot 2 \cdot 10)
Space Complexity: O(\log n \cdot 2^{10} \cdot 2)

1012. Numbers With Repeated Digits LeetCode Solution in C++

class Solution {
 public:
  int numDupDigitsAtMostN(int n) {
    return n - countSpecialNumbers(n);
  }

 private:
  // Same as 2376. Count Special Integers
  int countSpecialNumbers(int n) {
    const int digitSize = log10(n) + 1;
    vector<vector<vector<int>>> mem(
        digitSize + 1, vector<vector<int>>(1 << 10, vector<int>(2, -1)));
    return count(to_string(n), 0, 0, true, mem) - 1;  // - 0;
  }

 private:
  // Returns the number of special integers, considering the i-th digit, where
  // `used` is the bitmask of the used digits, and `isTight` indicates if the
  // current digit is tightly bound.
  int count(const string& s, int i, int used, bool isTight,
            vector<vector<vector<int>>>& mem) {
    if (i == s.length())
      return 1;
    if (mem[i][used][isTight] != -1)
      return mem[i][used][isTight];

    int res = 0;
    const int maxDigit = isTight ? s[i] - '0' : 9;

    for (int d = 0; d <= maxDigit; ++d) {
      // `d` is used.
      if (used >> d & 1)
        continue;
      // Use `d` now.
      const bool nextIsTight = isTight && (d == maxDigit);
      if (used == 0 && d == 0)  // Don't count leading 0s as used.
        res += count(s, i + 1, used, nextIsTight, mem);
      else
        res += count(s, i + 1, used | 1 << d, nextIsTight, mem);
    }

    return mem[i][used][isTight] = res;
  }
};
/* code provided by PROGIEZ */

1012. Numbers With Repeated Digits LeetCode Solution in Java

class Solution {
  public int numDupDigitsAtMostN(int n) {
    return n - countSpecialNumbers(n);
  }

  // Same as 2376. Count Special Integers
  private int countSpecialNumbers(int n) {
    final int digitSize = (int) Math.log10(n) + 1;
    Integer[][][] mem = new Integer[digitSize + 1][1 << 10][2];
    return count(String.valueOf(n), 0, 0, true, mem) - 1; // - 0;
  }

  // Returns the number of special integers, considering the i-th digit, where
  // `used` is the bitmask of the used digits, and `isTight` indicates if the
  // current digit is tightly bound.
  private int count(final String s, int i, int used, boolean isTight, Integer[][][] mem) {
    if (i == s.length())
      return 1;
    if (mem[i][used][isTight ? 1 : 0] != null)
      return mem[i][used][isTight ? 1 : 0];

    int res = 0;
    final int maxDigit = isTight ? s.charAt(i) - '0' : 9;

    for (int d = 0; d <= maxDigit; ++d) {
      // `d` is used.
      if ((used >> d & 1) == 1)
        continue;
      // Use `d` now.
      final boolean nextIsTight = isTight && (d == maxDigit);
      if (used == 0 && d == 0) // Don't count leading 0s as used.
        res += count(s, i + 1, used, nextIsTight, mem);
      else
        res += count(s, i + 1, used | 1 << d, nextIsTight, mem);
    }

    return mem[i][used][isTight ? 1 : 0] = res;
  }
}
// code provided by PROGIEZ

1012. Numbers With Repeated Digits LeetCode Solution in Python

class Solution:
  def numDupDigitsAtMostN(self, n: int) -> int:
    return n - self._countSpecialNumbers(n)

  # Same as 2376. Count Special Integers
  def _countSpecialNumbers(self, n: int) -> int:
    s = str(n)

    @functools.lru_cache(None)
    def dp(i: int, used: int, isTight: bool) -> int:
      """
      Returns the number of special integers, considering the i-th digit, where
      `used` is the bitmask of the used digits, and `isTight` indicates if the
      current digit is tightly bound.
      """
      if i == len(s):
        return 1

      res = 0
      maxDigit = int(s[i]) if isTight else 9

      for d in range(maxDigit + 1):
        # `d` is used.
        if used >> d & 1:
          continue
        # Use `d` now.
        nextIsTight = isTight and (d == maxDigit)
        if used == 0 and d == 0:  # Don't count leading 0s as used.
          res += dp(i + 1, used, nextIsTight)
        else:
          res += dp(i + 1, used | 1 << d, nextIsTight)

      return res

    return dp(0, 0, True) - 1  # - 0
 # code by PROGIEZ