Welcome to Subscribe On Youtube

1012. Numbers With Repeated Digits

Description

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

Solutions

• Java
• C++
• Python
• Go
• TypeScript

• class Solution {
      private int[] nums = new int[11];
      private Integer[][] dp = new Integer[11][1 << 11];
  
      public int numDupDigitsAtMostN(int n) {
          return n - f(n);
      }
  
      private int f(int n) {
          int i = -1;
          for (; n > 0; n /= 10) {
              nums[++i] = n % 10;
          }
          return dfs(i, 0, true, true);
      }
  
      private int dfs(int pos, int mask, boolean lead, boolean limit) {
          if (pos < 0) {
              return lead ? 0 : 1;
          }
          if (!lead && !limit && dp[pos][mask] != null) {
              return dp[pos][mask];
          }
          int ans = 0;
          int up = limit ? nums[pos] : 9;
          for (int i = 0; i <= up; ++i) {
              if ((mask >> i & 1) == 1) {
                  continue;
              }
              if (i == 0 && lead) {
                  ans += dfs(pos - 1, mask, lead, limit && i == up);
              } else {
                  ans += dfs(pos - 1, mask | 1 << i, false, limit && i == up);
              }
          }
          if (!lead && !limit) {
              dp[pos][mask] = ans;
          }
          return ans;
      }
  }
  

• class Solution {
  public:
      int numDupDigitsAtMostN(int n) {
          return n - f(n);
      }
  
  private:
      int nums[11];
      int dp[11][1 << 11];
  
      int f(int n) {
          memset(dp, -1, sizeof(dp));
          int i = -1;
          for (; n; n /= 10) {
              nums[++i] = n % 10;
          }
          return dfs(i, 0, true, true);
      }
  
      int dfs(int pos, int mask, bool lead, bool limit) {
          if (pos < 0) {
              return lead ? 0 : 1;
          }
          if (!lead && !limit && dp[pos][mask] != -1) {
              return dp[pos][mask];
          }
          int up = limit ? nums[pos] : 9;
          int ans = 0;
          for (int i = 0; i <= up; ++i) {
              if (mask >> i & 1) {
                  continue;
              }
              if (i == 0 && lead) {
                  ans += dfs(pos - 1, mask, lead, limit && i == up);
              } else {
                  ans += dfs(pos - 1, mask | 1 << i, false, limit && i == up);
              }
          }
          if (!lead && !limit) {
              dp[pos][mask] = ans;
          }
          return ans;
      }
  };
  

• class Solution:
      def numDupDigitsAtMostN(self, n: int) -> int:
          return n - self.f(n)
  
      def f(self, n: int) -> int:
          @cache
          def dfs(pos: int, mask: int, lead: bool, limit: bool) -> int:
              if pos < 0:
                  return int(lead) ^ 1
              up = nums[pos] if limit else 9
              ans = 0
              for i in range(up + 1):
                  if mask >> i & 1:
                      continue
                  if i == 0 and lead:
                      ans += dfs(pos - 1, mask, lead, limit and i == up)
                  else:
                      ans += dfs(pos - 1, mask | 1 << i, False, limit and i == up)
              return ans
  
          nums = []
          while n:
              nums.append(n % 10)
              n //= 10
          return dfs(len(nums) - 1, 0, True, True)
  
  

• func numDupDigitsAtMostN(n int) int {
  	return n - f(n)
  }
  
  func f(n int) int {
  	nums := []int{}
  	for ; n > 0; n /= 10 {
  		nums = append(nums, n%10)
  	}
  	dp := [11][1 << 11]int{}
  	for i := range dp {
  		for j := range dp[i] {
  			dp[i][j] = -1
  		}
  	}
  	var dfs func(int, int, bool, bool) int
  	dfs = func(pos int, mask int, lead bool, limit bool) int {
  		if pos < 0 {
  			if lead {
  				return 0
  			}
  			return 1
  		}
  		if !lead && !limit && dp[pos][mask] != -1 {
  			return dp[pos][mask]
  		}
  		up := 9
  		if limit {
  			up = nums[pos]
  		}
  		ans := 0
  		for i := 0; i <= up; i++ {
  			if mask>>i&1 == 1 {
  				continue
  			}
  			if i == 0 && lead {
  				ans += dfs(pos-1, mask, lead, limit && i == up)
  			} else {
  				ans += dfs(pos-1, mask|1<<i, false, limit && i == up)
  			}
  		}
  		if !lead && !limit {
  			dp[pos][mask] = ans
  		}
  		return ans
  	}
  	return dfs(len(nums)-1, 0, true, true)
  }
  

• function numDupDigitsAtMostN(n: number): number {
      return n - f(n);
  }
  
  function f(n: number): number {
      const nums: number[] = [];
      let i = -1;
      for (; n; n = Math.floor(n / 10)) {
          nums[++i] = n % 10;
      }
      const dp = Array.from({ length: 11 }, () => Array(1 << 11).fill(-1));
      const dfs = (pos: number, mask: number, lead: boolean, limit: boolean): number => {
          if (pos < 0) {
              return lead ? 0 : 1;
          }
          if (!lead && !limit && dp[pos][mask] !== -1) {
              return dp[pos][mask];
          }
          const up = limit ? nums[pos] : 9;
          let ans = 0;
          for (let i = 0; i <= up; ++i) {
              if ((mask >> i) & 1) {
                  continue;
              }
              if (lead && i === 0) {
                  ans += dfs(pos - 1, mask, lead, limit && i === up);
              } else {
                  ans += dfs(pos - 1, mask | (1 << i), false, limit && i === up);
              }
          }
          if (!lead && !limit) {
              dp[pos][mask] = ans;
          }
          return ans;
      };
      return dfs(i, 0, true, true);
  }
  
  

All Problems

All Solutions