Jobs

Interviews

Discussions

Numbers With Repeated Digits

Hard

Asked by:

16 views

Topics:

Dynamic ProgrammingRecursionArrays

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 <= 10⁹

Try coding it in LeetCode

Numbers With Repeated Digits

Hard

Asked by:

16 views

Topics:

Dynamic ProgrammingRecursionArrays

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 <= 10⁹

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the upper bound of the input number, and what data type should I use to represent it (e.g., 32-bit integer, 64-bit integer, or a string)?
Should I handle the case where the input number is 0?
If no numbers with repeated digits exist within the given range, what should I return?
Do you want the count of numbers with repeated digits or the actual numbers themselves?
Is the input inclusive, meaning should I consider the lower and upper bounds when counting?

Brute Force Solution

Approach

To find numbers with repeated digits, we'll simply check every number from 1 up to the given number. For each number, we'll see if it has any repeated digits by comparing each digit to all the other digits in the number.

Here's how the algorithm would work step-by-step:

Start with the number 1.
Check if the number 1 has any repeated digits. Since it only has one digit, it cannot have repeated digits.
Move on to the next number, 2.
Check if the number 2 has any repeated digits. Again, it only has one digit, so it cannot have repeated digits.
Keep increasing the number and checking each one for repeated digits.
For each number, look at its digits one by one.
Compare each digit to all the other digits in the number.
If you find any two digits that are the same, then the number has repeated digits.
If you reach the given number, stop.
Count how many numbers you found that have repeated digits.

Code Implementation

def numbers_with_repeated_digits_brute_force(limit):
    repeated_digit_count = 0

    for number in range(1, limit + 1):
        number_string = str(number)
        number_length = len(number_string)
        has_repeated_digit = False

        # Iterate over each digit in the number.
        for first_digit_index in range(number_length):
            for second_digit_index in range(first_digit_index + 1, number_length):
                # Check if any two digits are the same.
                if number_string[first_digit_index] == number_string[second_digit_index]:
                    has_repeated_digit = True
                    break
            if has_repeated_digit:
                break

        # Increment the count if repeated digits are found
        if has_repeated_digit:
            repeated_digit_count += 1

    return repeated_digit_count

Big(O) Analysis

Time Complexity

O(n log² n) – The algorithm iterates from 1 up to n. For each number i, it converts the number to its digits, which takes O(log i) time since the number of digits grows logarithmically with the number. Then, it compares each digit with every other digit within the number. Since the number of digits is at most log i, this comparison takes O((log i)²) time. Thus the overall complexity is the sum of (log i)² for i from 1 to n, and since the logarithm grows slowly, it can be approximated by n log² n.

Space Complexity

O(1) – The provided algorithm iterates from 1 to N and, for each number, compares its digits to each other. This comparison seems to be done in place, without creating any additional data structures that scale with the input N. The digit comparisons might involve a fixed number of variables to hold the digits being compared, but this number is independent of N. Therefore, the space complexity is constant, O(1).

Optimal Solution

Approach

The goal is to count numbers with repeating digits efficiently. We'll count the numbers that *don't* have repeating digits and subtract that from the total, as this is much easier to compute. This avoids checking every single number within the range.

Here's how the algorithm would work step-by-step:

Given a number, first figure out how many numbers smaller than it have repeating digits by counting those without repeating digits.
For numbers with fewer digits than the given number, calculating the count of numbers without repeating digits is straightforward.
For numbers with the same number of digits, consider each digit position from left to right.
At each digit position, determine how many choices are available for a digit that doesn't repeat any previous digits.
If the given number's digit at that position has already been used, stop counting for that branch.
Keep track of the number of unique digits that have already been used.
Carefully handle leading zeros to ensure correct counting.
Subtract the count of numbers *without* repeating digits from the total number of numbers in the range to find those *with* repeating digits.

Code Implementation

def numbers_with_repeated_digits(number):    number_string = str(number)
    number_length = len(number_string)
    
    def count_numbers_without_repeating_digits(length):
        if length == 0:
            return 0
        
        result = 9
        for available_digits in range(length - 1):
            result *= (9 - available_digits)
        return result

    count_without_repeats = 0
    
    # Sum counts for numbers with length less than input number
    for length in range(1, number_length):
        count_without_repeats += count_numbers_without_repeating_digits(length)
    
    used_digits = set()
    
    # Iterate through the digits of the number
    for index, digit_char in enumerate(number_string):
        digit = int(digit_char)
        
        # Iterate through available digits for current position
        for available_digit in range((0 if index > 0 else 1), digit):
            if available_digit not in used_digits:
                remaining_length = number_length - index - 1

                # Calculate combinations for remaining digits
                available_choices = 9 - len(used_digits)
                temp_result = 1
                for _ in range(remaining_length):
                    temp_result *= available_choices
                    available_choices -= 1
                count_without_repeats += temp_result

        # If the digit is already used, stop this branch
        if digit in used_digits:
            return number - count_without_repeats

        used_digits.add(digit)

    # Check if the original number has repeating digits
    if len(used_digits) == number_length:
        count_without_repeats += 1

    # Subtract numbers without repeating digits from total
    return number - count_without_repeats

Big(O) Analysis

Time Complexity

O(log n) – The algorithm's runtime is determined by the number of digits in the input number 'n'. We iterate through each digit of 'n' when calculating numbers without repeating digits. The number of digits in 'n' is proportional to log(n) (base 10), as each digit represents a power of 10. Therefore, the time complexity is O(log n) because the number of iterations grows logarithmically with the input number.

Space Complexity

O(1) – The algorithm's space complexity stems primarily from the 'used' digits set mentioned in step 6, which at most holds the unique digits from 0-9. This set doesn't grow with the input number N. Temporary variables might be used during computation, but their space usage remains constant irrespective of the input size N. Thus, the auxiliary space used is constant and does not depend on N.

Edge Cases

Case	How to Handle
Input N is 0	Return 0 since there are no numbers with repeated digits less than or equal to 0.
Input N is a single-digit number (1-9)	Return 0 since single digit numbers have no repeated digits.
Input N is a number with all identical digits (e.g., 111, 2222)	The algorithm should correctly count this as a number without repeated digits if it doesn't contain repeats; should work by computing total numbers without repeats and subtracting from N.
Input N consists of all 9s (e.g. 9, 99, 999)	Ensure the algorithm handles the transition between number of digits without overflow errors.
Input N is a number just below a power of 10 (e.g., 99, 9999)	This tests the algorithm's handling of numbers with many distinct digits.
Input N contains leading zeros (e.g. 0123, should be treated as 123)	Input should be treated as an integer, so leading zeros are irrelevant.
Large input N (close to maximum integer value)	The algorithm should be efficient in terms of time complexity and not cause an integer overflow during calculation.
Numbers containing zero as a repeated digit	The algorithm needs to correctly handle the constraint that the first digit cannot be zero when counting permutations without repeats.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the upper bound of the input number, and what data type should I use to represent it (e.g., 32-bit integer, 64-bit integer, or a string)?
Should I handle the case where the input number is 0?
If no numbers with repeated digits exist within the given range, what should I return?
Do you want the count of numbers with repeated digits or the actual numbers themselves?
Is the input inclusive, meaning should I consider the lower and upper bounds when counting?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start with the number 1.
Check if the number 1 has any repeated digits. Since it only has one digit, it cannot have repeated digits.
Move on to the next number, 2.
Check if the number 2 has any repeated digits. Again, it only has one digit, so it cannot have repeated digits.
Keep increasing the number and checking each one for repeated digits.
For each number, look at its digits one by one.
Compare each digit to all the other digits in the number.
If you find any two digits that are the same, then the number has repeated digits.
If you reach the given number, stop.
Count how many numbers you found that have repeated digits.

Code Implementation

def numbers_with_repeated_digits_brute_force(limit):
    repeated_digit_count = 0

    for number in range(1, limit + 1):
        number_string = str(number)
        number_length = len(number_string)
        has_repeated_digit = False

        # Iterate over each digit in the number.
        for first_digit_index in range(number_length):
            for second_digit_index in range(first_digit_index + 1, number_length):
                # Check if any two digits are the same.
                if number_string[first_digit_index] == number_string[second_digit_index]:
                    has_repeated_digit = True
                    break
            if has_repeated_digit:
                break

        # Increment the count if repeated digits are found
        if has_repeated_digit:
            repeated_digit_count += 1

    return repeated_digit_count

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Given a number, first figure out how many numbers smaller than it have repeating digits by counting those without repeating digits.
For numbers with fewer digits than the given number, calculating the count of numbers without repeating digits is straightforward.
For numbers with the same number of digits, consider each digit position from left to right.
At each digit position, determine how many choices are available for a digit that doesn't repeat any previous digits.
If the given number's digit at that position has already been used, stop counting for that branch.
Keep track of the number of unique digits that have already been used.
Carefully handle leading zeros to ensure correct counting.
Subtract the count of numbers *without* repeating digits from the total number of numbers in the range to find those *with* repeating digits.

Code Implementation

def numbers_with_repeated_digits(number):    number_string = str(number)
    number_length = len(number_string)
    
    def count_numbers_without_repeating_digits(length):
        if length == 0:
            return 0
        
        result = 9
        for available_digits in range(length - 1):
            result *= (9 - available_digits)
        return result

    count_without_repeats = 0
    
    # Sum counts for numbers with length less than input number
    for length in range(1, number_length):
        count_without_repeats += count_numbers_without_repeating_digits(length)
    
    used_digits = set()
    
    # Iterate through the digits of the number
    for index, digit_char in enumerate(number_string):
        digit = int(digit_char)
        
        # Iterate through available digits for current position
        for available_digit in range((0 if index > 0 else 1), digit):
            if available_digit not in used_digits:
                remaining_length = number_length - index - 1

                # Calculate combinations for remaining digits
                available_choices = 9 - len(used_digits)
                temp_result = 1
                for _ in range(remaining_length):
                    temp_result *= available_choices
                    available_choices -= 1
                count_without_repeats += temp_result

        # If the digit is already used, stop this branch
        if digit in used_digits:
            return number - count_without_repeats

        used_digits.add(digit)

    # Check if the original number has repeating digits
    if len(used_digits) == number_length:
        count_without_repeats += 1

    # Subtract numbers without repeating digits from total
    return number - count_without_repeats

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input N is 0	Return 0 since there are no numbers with repeated digits less than or equal to 0.
Input N is a single-digit number (1-9)	Return 0 since single digit numbers have no repeated digits.
Input N is a number with all identical digits (e.g., 111, 2222)	The algorithm should correctly count this as a number without repeated digits if it doesn't contain repeats; should work by computing total numbers without repeats and subtracting from N.
Input N consists of all 9s (e.g. 9, 99, 999)	Ensure the algorithm handles the transition between number of digits without overflow errors.
Input N is a number just below a power of 10 (e.g., 99, 9999)	This tests the algorithm's handling of numbers with many distinct digits.
Input N contains leading zeros (e.g. 0123, should be treated as 123)	Input should be treated as an integer, so leading zeros are irrelevant.
Large input N (close to maximum integer value)	The algorithm should be efficient in terms of time complexity and not cause an integer overflow during calculation.
Numbers containing zero as a repeated digit	The algorithm needs to correctly handle the constraint that the first digit cannot be zero when counting permutations without repeats.