Jobs

Interviews

Discussions

Count Good Numbers

Medium

Asked by:

More companies

43 views

Topics:

Dynamic ProgrammingRecursionBit Manipulation

A digit string is good if the digits (0-indexed) at even indices are even and the digits at odd indices are prime (2, 3, 5, or 7).

For example, "2582" is good because the digits (2 and 8) at even positions are even and the digits (5 and 2) at odd positions are prime. However, "3245" is not good because 3 is at an even index but is not even.

Given an integer n, return the total number of good digit strings of length n. Since the answer may be large, return it modulo 10⁹ + 7.

A digit string is a string consisting of digits 0 through 9 that may contain leading zeros.

Example 1:

Input: n = 1
Output: 5
Explanation: The good numbers of length 1 are "0", "2", "4", "6", "8".

Example 2:

Input: n = 4
Output: 400

Example 3:

Input: n = 50
Output: 564908303

Constraints:

1 <= n <= 10¹⁵

Try coding it in LeetCode

Count Good Numbers

Medium

Asked by:

43 views

Topics:

Dynamic ProgrammingRecursionBit Manipulation

A digit string is good if the digits (0-indexed) at even indices are even and the digits at odd indices are prime (2, 3, 5, or 7).

For example, "2582" is good because the digits (2 and 8) at even positions are even and the digits (5 and 2) at odd positions are prime. However, "3245" is not good because 3 is at an even index but is not even.

Given an integer n, return the total number of good digit strings of length n. Since the answer may be large, return it modulo 10⁹ + 7.

A digit string is a string consisting of digits 0 through 9 that may contain leading zeros.

Example 1:

Input: n = 1
Output: 5
Explanation: The good numbers of length 1 are "0", "2", "4", "6", "8".

Example 2:

Input: n = 4
Output: 400

Example 3:

Input: n = 50
Output: 564908303

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 range of values for 'n'? Is it possible for 'n' to be zero?
Are we only concerned with positive integer values of 'n'?
What is the desired output format? Should I return the result modulo some value to prevent overflow?
Could you clarify what constitutes a 'good number' more precisely? Does it explicitly refer to even digits in even places and odd digits in odd places?
Are there any specific edge cases I should be aware of, such as when n is 1 or 2?

Brute Force Solution

Approach

The brute force approach to counting good numbers involves checking every single possible number with a specific number of digits to see if it meets the criteria. We systematically generate each candidate number and test it. This is guaranteed to find the answer, but it may take a long time.

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

Generate the first possible number with the required number of digits.
Check if the number is 'good' by making sure digits at even positions are even and digits at odd positions are odd.
If the number is good, increase the count of good numbers.
Generate the next possible number with the required number of digits.
Repeat the checking process until all possible numbers with the required number of digits have been examined.
The final count is the total number of 'good' numbers found.

Code Implementation

def count_good_numbers_brute_force(number_of_digits):
    start_number = 10 ** (number_of_digits - 1)
    end_number = (10 ** number_of_digits) - 1
    good_numbers_count = 0

    # Iterate through every number within specified digit range.
    for current_number in range(start_number, end_number + 1):
        is_good = True
        number_as_string = str(current_number)

        #Check the 'good' criteria (even positions even, odd positions odd).
        for index, digit in enumerate(number_as_string):
            digit_value = int(digit)
            if index % 2 == 0 and digit_value % 2 != 0:
                is_good = False
                break

            if index % 2 != 0 and digit_value % 2 == 0:
                is_good = False
                break

        # Increment the count if the number meets 'good' criteria
        if is_good:
            good_numbers_count += 1

    return good_numbers_count

Big(O) Analysis

Time Complexity

O(10^n) – The brute force approach iterates through all possible n-digit numbers. There are 10^n such numbers since each digit can be 0-9. For each of these numbers, we must check if it is 'good', which takes O(n) time in the worst case. Therefore, the overall time complexity is O(n * 10^n). However, as n grows, 10^n term dominates n and it can be viewed as O(10^n).

Space Complexity

O(1) – The brute force approach, as described, generates numbers one at a time and checks if they are 'good'. It doesn't require storing all generated numbers or any significant intermediate data. The dominant space usage comes from a counter variable and potentially a temporary variable to hold the currently generated number, but their size is constant regardless of N (the number of digits). Therefore, the auxiliary space complexity is constant.

Optimal Solution

Approach

Instead of checking every possible number, the optimal approach uses math and a divide-and-conquer strategy to count the 'good' numbers quickly. We can break down the problem into smaller, easier-to-solve pieces and then combine the results efficiently.

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

Recognize that certain positions in the number can only have specific digits to be considered a 'good' number.
Figure out how many choices there are for each of those positions: even digits for even positions, and prime digits for odd positions.
Since each position's digit choice is independent, calculate the number of even/odd positions respectively.
Use exponentiation by squaring, a fast mathematical trick, to compute the total number of 'good' numbers for each set of positions.
Multiply the number of combinations of the even digits with the number of combinations of the odd digits, giving the total possible 'good' numbers.

Code Implementation

def count_good_numbers(number):    modulo = 10**9 + 7
    def fast_power(base, power):        result = 1
        while power > 0:
            if power % 2 == 1
                result = (result * base) % modulo
            base = (base * base) % modulo
            power //= 2
        return result
    #Even position can have 5 choices 0,2,4,6,8
    even_digit_choices = 5
    #Odd positions can have 4 choices 2,3,5,7
    odd_digit_choices = 4
    number_of_even_positions = (number + 1) // 2
    number_of_odd_positions = number // 2
    # Calculating the combinations using exponentiation by squaring
    even_combinations = fast_power(even_digit_choices, number_of_even_positions)
    odd_combinations = fast_power(odd_digit_choices, number_of_odd_positions)
    # Multiplying even and odd combinations to calculate final answer
    total_good_numbers = (even_combinations * odd_combinations) % modulo
    return total_good_numbers

Big(O) Analysis

Time Complexity

O(log n) – The dominant operation is exponentiation by squaring, which is used to calculate the power of the number of even digits and the number of odd digits. Exponentiation by squaring involves repeatedly squaring the base and halving the exponent. Therefore, the number of operations is proportional to the number of times n can be divided by 2, which is logarithmic. Thus the time complexity is O(log n).

Space Complexity

O(log N) – The primary space usage comes from the exponentiation by squaring, a divide-and-conquer approach. The recursion depth in this function dictates the space complexity, and in exponentiation by squaring, the depth is logarithmic with respect to the exponent, N. Therefore, the space complexity is O(log N) due to the recursion stack. No significant auxiliary data structures are allocated other than the implicit call stack.

Edge Cases

Case	How to Handle
n = 0	Return 1 since there is one way to form a 'good' number of length 0 (empty string).
n = 1	Return 5 since any of the odd digits (1, 3, 5, 7, 9) can occupy the first position.
Large value of n causing potential integer overflow	Use modular exponentiation with long type or BigInteger to prevent overflow.
n is a very large even number	Modular exponentiation will handle arbitrarily large even numbers efficiently, as it breaks down the exponent.
n is a very large odd number	Modular exponentiation handles large odd numbers by calculating base^(n-1) * base.
Result overflows after multiplying even and odd powers	Apply the modulo operator after each multiplication to prevent intermediate overflow.
Modulo is 1	Return 0, as every number modulo 1 will be 0.
n is negative	Treat as invalid input and throw an exception or return a predefined error value (e.g., -1).

n = 0

How to Handle:

Return 1 since there is one way to form a 'good' number of length 0 (empty string).

n = 1

How to Handle:

Return 5 since any of the odd digits (1, 3, 5, 7, 9) can occupy the first position.

Large value of n causing potential integer overflow

How to Handle:

Use modular exponentiation with long type or BigInteger to prevent overflow.

n is a very large even number

How to Handle:

Modular exponentiation will handle arbitrarily large even numbers efficiently, as it breaks down the exponent.

n is a very large odd number

How to Handle:

Modular exponentiation handles large odd numbers by calculating base^(n-1) * base.

Result overflows after multiplying even and odd powers

How to Handle:

Apply the modulo operator after each multiplication to prevent intermediate overflow.

Modulo is 1

How to Handle:

Return 0, as every number modulo 1 will be 0.

n is negative

How to Handle:

Treat as invalid input and throw an exception or return a predefined error value (e.g., -1).

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 range of values for 'n'? Is it possible for 'n' to be zero?
Are we only concerned with positive integer values of 'n'?
What is the desired output format? Should I return the result modulo some value to prevent overflow?
Could you clarify what constitutes a 'good number' more precisely? Does it explicitly refer to even digits in even places and odd digits in odd places?
Are there any specific edge cases I should be aware of, such as when n is 1 or 2?

Brute Force Solution

Approach

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

Generate the first possible number with the required number of digits.
Check if the number is 'good' by making sure digits at even positions are even and digits at odd positions are odd.
If the number is good, increase the count of good numbers.
Generate the next possible number with the required number of digits.
Repeat the checking process until all possible numbers with the required number of digits have been examined.
The final count is the total number of 'good' numbers found.

Code Implementation

def count_good_numbers_brute_force(number_of_digits):
    start_number = 10 ** (number_of_digits - 1)
    end_number = (10 ** number_of_digits) - 1
    good_numbers_count = 0

    # Iterate through every number within specified digit range.
    for current_number in range(start_number, end_number + 1):
        is_good = True
        number_as_string = str(current_number)

        #Check the 'good' criteria (even positions even, odd positions odd).
        for index, digit in enumerate(number_as_string):
            digit_value = int(digit)
            if index % 2 == 0 and digit_value % 2 != 0:
                is_good = False
                break

            if index % 2 != 0 and digit_value % 2 == 0:
                is_good = False
                break

        # Increment the count if the number meets 'good' criteria
        if is_good:
            good_numbers_count += 1

    return good_numbers_count

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Recognize that certain positions in the number can only have specific digits to be considered a 'good' number.
Figure out how many choices there are for each of those positions: even digits for even positions, and prime digits for odd positions.
Since each position's digit choice is independent, calculate the number of even/odd positions respectively.
Use exponentiation by squaring, a fast mathematical trick, to compute the total number of 'good' numbers for each set of positions.
Multiply the number of combinations of the even digits with the number of combinations of the odd digits, giving the total possible 'good' numbers.

Code Implementation

def count_good_numbers(number):    modulo = 10**9 + 7
    def fast_power(base, power):        result = 1
        while power > 0:
            if power % 2 == 1
                result = (result * base) % modulo
            base = (base * base) % modulo
            power //= 2
        return result
    #Even position can have 5 choices 0,2,4,6,8
    even_digit_choices = 5
    #Odd positions can have 4 choices 2,3,5,7
    odd_digit_choices = 4
    number_of_even_positions = (number + 1) // 2
    number_of_odd_positions = number // 2
    # Calculating the combinations using exponentiation by squaring
    even_combinations = fast_power(even_digit_choices, number_of_even_positions)
    odd_combinations = fast_power(odd_digit_choices, number_of_odd_positions)
    # Multiplying even and odd combinations to calculate final answer
    total_good_numbers = (even_combinations * odd_combinations) % modulo
    return total_good_numbers

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
n = 0	Return 1 since there is one way to form a 'good' number of length 0 (empty string).
n = 1	Return 5 since any of the odd digits (1, 3, 5, 7, 9) can occupy the first position.
Large value of n causing potential integer overflow	Use modular exponentiation with long type or BigInteger to prevent overflow.
n is a very large even number	Modular exponentiation will handle arbitrarily large even numbers efficiently, as it breaks down the exponent.
n is a very large odd number	Modular exponentiation handles large odd numbers by calculating base^(n-1) * base.
Result overflows after multiplying even and odd powers	Apply the modulo operator after each multiplication to prevent intermediate overflow.
Modulo is 1	Return 0, as every number modulo 1 will be 0.
n is negative	Treat as invalid input and throw an exception or return a predefined error value (e.g., -1).

n = 0

How to Handle:

Return 1 since there is one way to form a 'good' number of length 0 (empty string).

n = 1

How to Handle:

Return 5 since any of the odd digits (1, 3, 5, 7, 9) can occupy the first position.

Large value of n causing potential integer overflow

How to Handle:

Use modular exponentiation with long type or BigInteger to prevent overflow.

n is a very large even number

How to Handle:

Modular exponentiation will handle arbitrarily large even numbers efficiently, as it breaks down the exponent.

n is a very large odd number

How to Handle:

Modular exponentiation handles large odd numbers by calculating base^(n-1) * base.

Result overflows after multiplying even and odd powers

How to Handle:

Apply the modulo operator after each multiplication to prevent intermediate overflow.

Modulo is 1

How to Handle:

Return 0, as every number modulo 1 will be 0.

n is negative

How to Handle:

Treat as invalid input and throw an exception or return a predefined error value (e.g., -1).