Numbers With Repeated Digits

Problem Description

Given an integer n, return the number of positive integers in the range [1, n] that have at least one repeated digit.

Key Insights

• A number has repeated digits if any digit appears more than once.
• Directly counting numbers with repeated digits can be inefficient for large n.
• We can instead count numbers without repeated digits and subtract from the total count.
• The range of n can be up to 10^9, which requires an efficient approach.

Space and Time Complexity

Time Complexity: O(1) for counting unique digit numbers, as it involves calculations based on the number of digits in n. Space Complexity: O(1), as we are using a fixed amount of space for variables regardless of the input size.

Solution

To solve this problem, we can use a combinatorial approach. The key idea is to count the numbers without repeated digits and then subtract that count from n. We can achieve this by:

1. Determining the number of digits in n.
2. Counting the unique digit numbers for each length shorter than n.
3. Handling the numbers with the same length as n by ensuring the digits chosen do not exceed the digits in n at each position.
4. Using a set or boolean array to track used digits while forming valid numbers.

Code Solutions