Jobs

Interviews

Discussions

Digit Count in Range

Hard

Asked by:

12 views

Topics:

Dynamic Programming

Given an integer d between 0 and 9, and two positive integers low and high as lower and upper bounds, respectively. Return the number of times that d occurs as a digit in all integers between low and high, inclusive.

Example 1:

Input: d = 1, low = 1, high = 13
Output: 6
Explanation: 
The digit d=1 occurs 6 times in 1, 10, 11, 12, 13.

Example 2:

Input: d = 3, low = 100, high = 250
Output: 35
Explanation: 
The digit d=3 occurs 35 times in 103, 113, 123, 130, 131, ..., 238, 239, 243.

Constraints:

0 <= d <= 9
1 <= low <= high <= 2 * 10⁸

Try coding it in LeetCode

Digit Count in Range

Hard

Asked by:

12 views

Topics:

Dynamic Programming

Example 1:

Input: d = 1, low = 1, high = 13
Output: 6
Explanation: 
The digit d=1 occurs 6 times in 1, 10, 11, 12, 13.

Example 2:

Input: d = 3, low = 100, high = 250
Output: 35
Explanation: 
The digit d=3 occurs 35 times in 103, 113, 123, 130, 131, ..., 238, 239, 243.

Constraints:

0 <= d <= 9
1 <= low <= high <= 2 * 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 are the inclusive ranges for the low and high input integers, and for the digit d?
Are the inputs low, high, and digit 'd' always non-negative integers?
What should I return if low is greater than high?
Is the digit 'd' guaranteed to be a single digit (0-9)?
Could you provide a small example to illustrate the expected behavior?

Brute Force Solution

Approach

The brute force approach to counting digits in a range involves examining every number within the given range. For each number, we'll inspect its digits and count how many times our target digit appears. This is a straightforward but potentially slow method.

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

Start by considering the first number in the range.
Check each digit in that number to see if it matches the digit we are looking for.
If a digit matches, increase our count.
Move on to the next number in the range.
Repeat the process of checking each digit and updating the count for this new number.
Keep repeating this process, number by number, until we reach the end of the specified range.
The final count will be the total number of times our target digit appeared within the entire range.

Code Implementation

def digit_count_in_range_brute_force(low_number, high_number, target_digit):
    digit_count = 0

    # Iterate through all numbers in the specified range
    for current_number in range(low_number, high_number + 1):
        number_string = str(current_number)

        # Iterate through the digits of the current number
        for digit_char in number_string:
            digit = int(digit_char)

            # Check if the digit matches the target digit
            if digit == target_digit:
                # Increment the digit count if it matches
                digit_count += 1

    return digit_count

Big(O) Analysis

Time Complexity

O(N * log10(high)) – The brute force approach iterates through each number in the range [low, high], where N = high - low + 1. For each number, we examine its digits. The number of digits in a number is proportional to log10(number). In the worst case, we examine log10(high) digits for each number. Thus, the overall time complexity is O(N * log10(high)).

Space Complexity

O(1) – The brute force approach iterates through a range of numbers and checks each digit within those numbers. It doesn't create any auxiliary data structures like arrays, lists, or hash maps to store intermediate results or track visited numbers. The only space used is for a few integer variables to hold the current number being examined, the target digit, and the digit count, which remains constant regardless of the size of the range (N). Therefore, the space complexity is O(1).

Optimal Solution

Approach

The efficient strategy is to count the occurrences of a digit within a range by cleverly breaking the range down digit by digit. We avoid checking every single number within the range directly. This approach cleverly uses math to avoid brute force.

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

First, create a function to count how many times the digit appears up to any single number.
To do this, process the digits of the number from right to left.
Consider how the count of the digit changes depending on whether the current digit we are looking at is larger than, smaller than, or equal to the digit we're counting.
Calculate the count for all positions within that digit in the current number.
Next, to solve the original problem, use the count function twice: once for the end of the range and once for the start of the range, then subtract the start count from the end count.

Code Implementation

def digit_count_in_range(
    lower_bound,
    upper_bound,
    digit_to_count):

    def count_digit_up_to_number(
        number,
        digit_to_count):

        string_number = str(number)
        number_length = len(string_number)
        count = 0

        for i in range(number_length):
            current_digit = int(string_number[i])
            power_of_ten = 10 ** (number_length - i - 1)

            # Calculate count when current digit is less than digit to count.
            if current_digit < digit_to_count:
                count += int(string_number[:i] or 0) * power_of_ten

            # Calculate count when current digit is greater than digit to count.
            elif current_digit > digit_to_count:
                count += (int(string_number[:i] or 0) + 1) * power_of_ten

            # When equal, add the remaining digits + 1.
            else:
                count += int(string_number[:i] or 0) * power_of_ten + \
                         int(string_number[i+1:] or 0) + 1

            #Exclude leading zeros if counting zeros.
            if digit_to_count == 0 and i == 0:
                count -= power_of_ten

        return count

    # Edge case: if lower bound is 0, avoid double counting.
    count_at_lower_bound = count_digit_up_to_number(
        lower_bound - 1,
        digit_to_count
    ) if lower_bound > 0 else 0

    count_at_upper_bound = count_digit_up_to_number(
        upper_bound,
        digit_to_count
    )

    # Subtract counts to get the count within the range.
    return count_at_upper_bound - count_at_lower_bound

Big(O) Analysis

Time Complexity

O(log n) – The solution's time complexity is determined by the number of digits in the input numbers (low and high), which is logarithmic with respect to the magnitude of the numbers (n). The count function iterates through the digits of a given number. Since the number of digits is logarithmic in the number's value, the count function takes O(log n) time. The overall solution calls this function twice. Thus the overall time complexity is O(log n).

Space Complexity

O(1) – The algorithm processes the digits of a number, but it doesn't store these digits in any auxiliary data structure like an array or a list. The count function primarily uses variables to store intermediate calculations such as the current digit, the count of the target digit, and powers of ten, all of which occupy constant space. Since no data structure grows with the size of the input number, the auxiliary space complexity is constant.

Edge Cases

Case	How to Handle
low and high are equal and digit appears in that number	Handle this case by checking if the digit exists in the single number and returning 1 or 0.
low is greater than high	Return 0 since there is no range.
digit is outside the range [0, 9]	Treat as invalid input and return 0 (or throw an error).
low and/or high are negative numbers	If negative numbers are not allowed, return 0 (or throw an error); otherwise handle correctly based on the intended behavior for negative ranges, considering the negative sign's impact on digit counts.
low is 0 and high is a very large number (e.g., Integer.MAX_VALUE)	Consider the computational cost and potential for optimization to avoid timeout due to the large iteration range.
digit is 0 and the range includes 0	Handle this case carefully since many numbers in the range will contain the digit 0.
low and high contain many occurrences of the digit	Ensure the algorithm correctly counts all occurrences without duplicates or omissions, especially when digits repeat within numbers.
Integer overflow in calculations	Use long data types or other methods to prevent overflow when calculating digit counts, especially with very large ranges.

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 are the inclusive ranges for the low and high input integers, and for the digit d?
Are the inputs low, high, and digit 'd' always non-negative integers?
What should I return if low is greater than high?
Is the digit 'd' guaranteed to be a single digit (0-9)?
Could you provide a small example to illustrate the expected behavior?

Brute Force Solution

Approach

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

Start by considering the first number in the range.
Check each digit in that number to see if it matches the digit we are looking for.
If a digit matches, increase our count.
Move on to the next number in the range.
Repeat the process of checking each digit and updating the count for this new number.
Keep repeating this process, number by number, until we reach the end of the specified range.
The final count will be the total number of times our target digit appeared within the entire range.

Code Implementation

def digit_count_in_range_brute_force(low_number, high_number, target_digit):
    digit_count = 0

    # Iterate through all numbers in the specified range
    for current_number in range(low_number, high_number + 1):
        number_string = str(current_number)

        # Iterate through the digits of the current number
        for digit_char in number_string:
            digit = int(digit_char)

            # Check if the digit matches the target digit
            if digit == target_digit:
                # Increment the digit count if it matches
                digit_count += 1

    return digit_count

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, create a function to count how many times the digit appears up to any single number.
To do this, process the digits of the number from right to left.
Consider how the count of the digit changes depending on whether the current digit we are looking at is larger than, smaller than, or equal to the digit we're counting.
Calculate the count for all positions within that digit in the current number.
Next, to solve the original problem, use the count function twice: once for the end of the range and once for the start of the range, then subtract the start count from the end count.

Code Implementation

def digit_count_in_range(
    lower_bound,
    upper_bound,
    digit_to_count):

    def count_digit_up_to_number(
        number,
        digit_to_count):

        string_number = str(number)
        number_length = len(string_number)
        count = 0

        for i in range(number_length):
            current_digit = int(string_number[i])
            power_of_ten = 10 ** (number_length - i - 1)

            # Calculate count when current digit is less than digit to count.
            if current_digit < digit_to_count:
                count += int(string_number[:i] or 0) * power_of_ten

            # Calculate count when current digit is greater than digit to count.
            elif current_digit > digit_to_count:
                count += (int(string_number[:i] or 0) + 1) * power_of_ten

            # When equal, add the remaining digits + 1.
            else:
                count += int(string_number[:i] or 0) * power_of_ten + \
                         int(string_number[i+1:] or 0) + 1

            #Exclude leading zeros if counting zeros.
            if digit_to_count == 0 and i == 0:
                count -= power_of_ten

        return count

    # Edge case: if lower bound is 0, avoid double counting.
    count_at_lower_bound = count_digit_up_to_number(
        lower_bound - 1,
        digit_to_count
    ) if lower_bound > 0 else 0

    count_at_upper_bound = count_digit_up_to_number(
        upper_bound,
        digit_to_count
    )

    # Subtract counts to get the count within the range.
    return count_at_upper_bound - count_at_lower_bound

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
low and high are equal and digit appears in that number	Handle this case by checking if the digit exists in the single number and returning 1 or 0.
low is greater than high	Return 0 since there is no range.
digit is outside the range [0, 9]	Treat as invalid input and return 0 (or throw an error).
low and/or high are negative numbers	If negative numbers are not allowed, return 0 (or throw an error); otherwise handle correctly based on the intended behavior for negative ranges, considering the negative sign's impact on digit counts.
low is 0 and high is a very large number (e.g., Integer.MAX_VALUE)	Consider the computational cost and potential for optimization to avoid timeout due to the large iteration range.
digit is 0 and the range includes 0	Handle this case carefully since many numbers in the range will contain the digit 0.
low and high contain many occurrences of the digit	Ensure the algorithm correctly counts all occurrences without duplicates or omissions, especially when digits repeat within numbers.
Integer overflow in calculations	Use long data types or other methods to prevent overflow when calculating digit counts, especially with very large ranges.