Scale Engineer

Numbers With Repeated Digits

Hard
#0966Time: O(n * log₁₀(n)). The main loop runs `n` times. For each number `i`, the `hasRepeatedDigits` function takes a number of steps proportional to the number of digits in `i`, which is `O(log₁₀(i))`. Given `n` can be up to 10⁹, this approach is too slow.Space: O(1). The space required for the `seen` array is constant as it always has a size of 10, regardless of the input `n`.2 companies
Patterns
MathDynamic Programming
Companies
IBMJ.P. Morgan

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves a straightforward iteration through every integer from 1 to n. For each integer, it performs a check to see if it contains any repeated digits. A counter is maintained and incremented for each number that is found to have at least one repeated digit.

Algorithm

  • Initialize a counter count to 0.
  • Loop through each integer i from 1 to n.
  • For each i, call a helper function hasRepeatedDigits(i).
  • If the helper function returns true, increment count.
  • Return count after the loop finishes.

Helper function hasRepeatedDigits(num):

  • Create a boolean array seen of size 10, initialized to false.
  • While num is greater than 0:
    • Extract the last digit: digit = num % 10.
    • If seen[digit] is already true, it means the digit is repeated, so return true.
    • Mark the digit as seen: seen[digit] = true.
    • Remove the last digit: num = num / 10.
  • If the loop completes without finding repeated digits, return false.

Walkthrough

The algorithm begins by initializing a counter, count, to zero. It then enters a loop that iterates through each number i from 1 up to the given integer n. Inside this loop, a helper function, hasRepeatedDigits(i), is invoked to determine if the current number i has any duplicate digits.

The hasRepeatedDigits function works by examining the digits of the number one by one. It uses a boolean array of size 10 as a frequency map to keep track of the digits it has already encountered. It extracts digits from the number using the modulo (%) and division (/) operators. If it encounters a digit that is already marked as seen in the frequency map, it immediately returns true, indicating a repeated digit. If it processes all digits without finding any repeats, it returns false.

Back in the main loop, if the helper function returns true, the count is incremented. After checking all numbers up to n, the final count is returned, which represents the total number of integers in the range [1, n] with at least one repeated digit.

class Solution {    public int numDupDigitsAtMostN(int n) {        int count = 0;        for (int i = 1; i <= n; i++) {            if (hasRepeatedDigits(i)) {                count++;            }        }        return count;    }     private boolean hasRepeatedDigits(int num) {        boolean[] seen = new boolean[10];        while (num > 0) {            int digit = num % 10;            if (seen[digit]) {                return true;            }            seen[digit] = true;            num /= 10;        }        return false;    }}

Complexity

Time

O(n * log₁₀(n)). The main loop runs `n` times. For each number `i`, the `hasRepeatedDigits` function takes a number of steps proportional to the number of digits in `i`, which is `O(log₁₀(i))`. Given `n` can be up to 10⁹, this approach is too slow.

Space

O(1). The space required for the `seen` array is constant as it always has a size of 10, regardless of the input `n`.

Trade-offs

Pros

  • Simple to understand and implement.

  • Correct for small values of n.

Cons

  • Highly inefficient for large values of n.

  • Will result in a 'Time Limit Exceeded' error on most platforms for the given constraints.

Solutions

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;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem