Jobs

Interviews

Discussions

Find the Count of Good Integers

Hard

Asked by:

26 views

Topics:

Dynamic ProgrammingRecursion

You are given two positive integers n and k.

An integer x is called k-palindromic if:

x is a palindrome.
x is divisible by k.

An integer is called good if its digits can be rearranged to form a k-palindromic integer. For example, for k = 2, 2020 can be rearranged to form the k-palindromic integer 2002, whereas 1010 cannot be rearranged to form a k-palindromic integer.

Return the count of good integers containing n digits.

Note that any integer must not have leading zeros, neither before nor after rearrangement. For example, 1010 cannot be rearranged to form 101.

Example 1:

Input: n = 3, k = 5

Output: 27

Explanation:

Some of the good integers are:

551 because it can be rearranged to form 515.
525 because it is already k-palindromic.

Example 2:

Input: n = 1, k = 4

Output: 2

Explanation:

The two good integers are 4 and 8.

Example 3:

Input: n = 5, k = 6

Output: 2468

Constraints:

1 <= n <= 10
1 <= k <= 9

Try coding it in LeetCode

Find the Count of Good Integers

Hard

Asked by:

26 views

Topics:

Dynamic ProgrammingRecursion

You are given two positive integers n and k.

An integer x is called k-palindromic if:

x is a palindrome.
x is divisible by k.

Return the count of good integers containing n digits.

Note that any integer must not have leading zeros, neither before nor after rearrangement. For example, 1010 cannot be rearranged to form 101.

Example 1:

Input: n = 3, k = 5

Output: 27

Explanation:

Some of the good integers are:

551 because it can be rearranged to form 515.
525 because it is already k-palindromic.

Example 2:

Input: n = 1, k = 4

Output: 2

Explanation:

The two good integers are 4 and 8.

Example 3:

Input: n = 5, k = 6

Output: 2468

Constraints:

1 <= n <= 10
1 <= k <= 9

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 constraints on the input integers (e.g., range, positive/negative/zero)?
How large can the input be, and should I be concerned about potential integer overflow during calculations?
What defines a "good integer" precisely? Are there any specific properties or conditions it must satisfy beyond what's stated in the problem description?
If no "good integer" exists, what should the function return (e.g., 0, -1, null)?
Are we looking for the count of distinct good integers, or is it possible to have the same good integer appear multiple times in a way that affects the count?

Brute Force Solution

Approach

The brute force approach to counting good integers is like checking every single number within the given range. We look at each number individually and determine if it fits our definition of a 'good' integer.

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

Start with the smallest number in the specified range.
Check if this number is a 'good' integer, based on whatever makes a number 'good' (e.g., its digits have certain properties).
If the number is 'good', increase a counter.
Move on to the next number in the range.
Repeat the 'check' and 'count' steps for every number until you reach the largest number in the range.
The final value of the counter will be the total count of 'good' integers.

Code Implementation

def count_good_integers_brute_force(start_number, end_number):    good_integers_count = 0
    # Iterate through each number in the specified range.
    for current_number in range(start_number, end_number + 1):
        # Check if the current number is a 'good' integer.
        if is_good_integer(current_number):

            good_integers_count += 1

    return good_integers_count

def is_good_integer(number):
    number_string = str(number)
    # Good integers consist only of digits 1, 2, and 3.
    for digit_character in number_string:
        digit = int(digit_character)
        if digit < 1 or digit > 3:
            return False

    return True

Big(O) Analysis

Time Complexity

O(n * k) – The brute force approach iterates through each number in the range of n integers. For each of these n integers, we perform a check to determine if it's a 'good' integer. The cost of this check depends on the number of digits, k, in each number because we have to examine each digit individually. Thus, in the worst-case scenario, we potentially analyze each of the n integers, and each analysis requires k steps, giving us n * k operations. Therefore, the time complexity is O(n * k).

Space Complexity

O(1) – The brute force approach, as described, iterates through a range of numbers and checks each one individually. It uses a single counter variable to keep track of the number of 'good' integers found. Regardless of the size of the range (which would be related to N), this algorithm does not allocate any additional data structures that scale with the input size. Therefore, the space complexity is constant.

Optimal Solution

Approach

The goal is to count numbers within a given range that only use certain digits. Instead of checking every single number in the range, we can be smarter by constructing 'good' numbers digit by digit, making sure we only use allowed digits.

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

First, handle some simple cases like when the range is empty or if the allowed digits are empty.
Break down the problem by considering the number of 'good' numbers with fewer digits than the upper limit of our range.
Now, focus on building numbers that have the same number of digits as the upper limit.
Start from the leftmost digit and consider each allowed digit. If an allowed digit is smaller than the corresponding digit in the upper limit, we know we can create a bunch of 'good' numbers using that allowed digit.
If an allowed digit is equal to the corresponding digit in the upper limit, we need to continue building our 'good' number and move to the next digit.
If an allowed digit is larger than the corresponding digit in the upper limit, we can't use it.
Repeat this process digit by digit. Keep track of how many 'good' numbers we've found.
Also, do a similar process starting from the lower limit of our range but adjust your counts to not include those before the range.

Code Implementation

def find_the_count_of_good_integers(
        lower_bound, upper_bound, allowed_digits):
    allowed_digits = sorted([int(digit) for digit in allowed_digits])

    def count_good_integers_less_than_or_equal_to(
            number, allowed_digits):
        number_as_string = str(number)
        number_length = len(number_as_string)
        count = 0

        # Count 'good' numbers with fewer digits than the given number.
        for length in range(1, number_length):
            count += len(allowed_digits) ** length

        # Build numbers with the same number of digits as the given number.
        for index, digit in enumerate(number_as_string):
            digit = int(digit)
            valid_digits = [d for d in allowed_digits if d < digit]
            count += len(valid_digits) * (
                len(allowed_digits) ** (number_length - index - 1))

            # If current digit not in allowed, stop.
            if digit not in allowed_digits:
                return count

            # If we reach the last digit, the number itself is valid.
            if index == number_length - 1:
                count += 1

        return count

    # Handle cases where bounds are equal to zero
    lower_bound_count = (
        count_good_integers_less_than_or_equal_to(
            lower_bound - 1, allowed_digits)
        if lower_bound > 1 else 0
    )

    # Subtract the count of good integers below lower bound to be inclusive.
    upper_bound_count = (
        count_good_integers_less_than_or_equal_to(
            upper_bound, allowed_digits))

    # Final calculation. We subtract to find count within the range.
    return upper_bound_count - lower_bound_count

Big(O) Analysis

Time Complexity

O(log(high)) – The dominant factor in the time complexity is determined by the number of digits in the upper bound (high) of the range, which we can consider as log10(high) or simply log(high). We iterate through the digits of the upper bound and lower bound, performing a constant amount of work for each digit. Since the number of digits is logarithmic with respect to the value of the high parameter, the overall time complexity is O(log(high)).

Space Complexity

O(D) – The space complexity is dominated by the recursion depth when building numbers digit by digit. In the worst-case scenario, we might need to explore all possible digits for each position up to the maximum number of digits (D) present in the upper limit of the range. This would lead to a recursion depth of D, where each recursive call requires space on the call stack for storing variables and the return address. Therefore, the auxiliary space used is proportional to the number of digits D in the upper limit, resulting in a space complexity of O(D).

Edge Cases

Case	How to Handle
Input 'n' is zero or negative.	Return 0 since a non-positive n indicates no valid integers can be formed.
Input 'n' is a single digit (0-9).	Return n+1, as all digits from 0 to n are considered 'good'.
Input 'n' has repeating digits, such as 33 or 777.	The algorithm must correctly handle these cases without double-counting.
Input 'n' contains digits not in the set {0, 1, 2, 5, 6, 8, 9}.	The recursive/iterative function must skip over or adjust the bound properly when checking a disallowed digit.
Input 'n' is a large number that approaches integer limits.	Ensure no integer overflow occurs during calculations or comparisons, potentially using long data types if needed.
n starts with an invalid digit (3,4,7).	The starting digit must be converted to the next valid digit to continue processing (e.g., 3->5).
n consists entirely of 'good' digits (e.g., 111, 222, 555).	The code counts these cases accurately as they are valid according to the definition.
All digits of 'n' are greater than 2, such as '9865'.	The algorithm must iterate and count through all combinations of good numbers less than each digit.

Input 'n' is zero or negative.

How to Handle:

Return 0 since a non-positive n indicates no valid integers can be formed.

Input 'n' is a single digit (0-9).

How to Handle:

Return n+1, as all digits from 0 to n are considered 'good'.

Input 'n' has repeating digits, such as 33 or 777.

How to Handle:

The algorithm must correctly handle these cases without double-counting.

Input 'n' contains digits not in the set {0, 1, 2, 5, 6, 8, 9}.

How to Handle:

The recursive/iterative function must skip over or adjust the bound properly when checking a disallowed digit.

Input 'n' is a large number that approaches integer limits.

How to Handle:

Ensure no integer overflow occurs during calculations or comparisons, potentially using long data types if needed.

n starts with an invalid digit (3,4,7).

How to Handle:

The starting digit must be converted to the next valid digit to continue processing (e.g., 3->5).

n consists entirely of 'good' digits (e.g., 111, 222, 555).

How to Handle:

The code counts these cases accurately as they are valid according to the definition.

All digits of 'n' are greater than 2, such as '9865'.

How to Handle:

The algorithm must iterate and count through all combinations of good numbers less than each digit.

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 constraints on the input integers (e.g., range, positive/negative/zero)?
How large can the input be, and should I be concerned about potential integer overflow during calculations?
What defines a "good integer" precisely? Are there any specific properties or conditions it must satisfy beyond what's stated in the problem description?
If no "good integer" exists, what should the function return (e.g., 0, -1, null)?
Are we looking for the count of distinct good integers, or is it possible to have the same good integer appear multiple times in a way that affects the count?

Brute Force Solution

Approach

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

Start with the smallest number in the specified range.
Check if this number is a 'good' integer, based on whatever makes a number 'good' (e.g., its digits have certain properties).
If the number is 'good', increase a counter.
Move on to the next number in the range.
Repeat the 'check' and 'count' steps for every number until you reach the largest number in the range.
The final value of the counter will be the total count of 'good' integers.

Code Implementation

def count_good_integers_brute_force(start_number, end_number):    good_integers_count = 0
    # Iterate through each number in the specified range.
    for current_number in range(start_number, end_number + 1):
        # Check if the current number is a 'good' integer.
        if is_good_integer(current_number):

            good_integers_count += 1

    return good_integers_count

def is_good_integer(number):
    number_string = str(number)
    # Good integers consist only of digits 1, 2, and 3.
    for digit_character in number_string:
        digit = int(digit_character)
        if digit < 1 or digit > 3:
            return False

    return True

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, handle some simple cases like when the range is empty or if the allowed digits are empty.
Break down the problem by considering the number of 'good' numbers with fewer digits than the upper limit of our range.
Now, focus on building numbers that have the same number of digits as the upper limit.
Start from the leftmost digit and consider each allowed digit. If an allowed digit is smaller than the corresponding digit in the upper limit, we know we can create a bunch of 'good' numbers using that allowed digit.
If an allowed digit is equal to the corresponding digit in the upper limit, we need to continue building our 'good' number and move to the next digit.
If an allowed digit is larger than the corresponding digit in the upper limit, we can't use it.
Repeat this process digit by digit. Keep track of how many 'good' numbers we've found.
Also, do a similar process starting from the lower limit of our range but adjust your counts to not include those before the range.

Code Implementation

def find_the_count_of_good_integers(
        lower_bound, upper_bound, allowed_digits):
    allowed_digits = sorted([int(digit) for digit in allowed_digits])

    def count_good_integers_less_than_or_equal_to(
            number, allowed_digits):
        number_as_string = str(number)
        number_length = len(number_as_string)
        count = 0

        # Count 'good' numbers with fewer digits than the given number.
        for length in range(1, number_length):
            count += len(allowed_digits) ** length

        # Build numbers with the same number of digits as the given number.
        for index, digit in enumerate(number_as_string):
            digit = int(digit)
            valid_digits = [d for d in allowed_digits if d < digit]
            count += len(valid_digits) * (
                len(allowed_digits) ** (number_length - index - 1))

            # If current digit not in allowed, stop.
            if digit not in allowed_digits:
                return count

            # If we reach the last digit, the number itself is valid.
            if index == number_length - 1:
                count += 1

        return count

    # Handle cases where bounds are equal to zero
    lower_bound_count = (
        count_good_integers_less_than_or_equal_to(
            lower_bound - 1, allowed_digits)
        if lower_bound > 1 else 0
    )

    # Subtract the count of good integers below lower bound to be inclusive.
    upper_bound_count = (
        count_good_integers_less_than_or_equal_to(
            upper_bound, allowed_digits))

    # Final calculation. We subtract to find count within the range.
    return upper_bound_count - lower_bound_count

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input 'n' is zero or negative.	Return 0 since a non-positive n indicates no valid integers can be formed.
Input 'n' is a single digit (0-9).	Return n+1, as all digits from 0 to n are considered 'good'.
Input 'n' has repeating digits, such as 33 or 777.	The algorithm must correctly handle these cases without double-counting.
Input 'n' contains digits not in the set {0, 1, 2, 5, 6, 8, 9}.	The recursive/iterative function must skip over or adjust the bound properly when checking a disallowed digit.
Input 'n' is a large number that approaches integer limits.	Ensure no integer overflow occurs during calculations or comparisons, potentially using long data types if needed.
n starts with an invalid digit (3,4,7).	The starting digit must be converted to the next valid digit to continue processing (e.g., 3->5).
n consists entirely of 'good' digits (e.g., 111, 222, 555).	The code counts these cases accurately as they are valid according to the definition.
All digits of 'n' are greater than 2, such as '9865'.	The algorithm must iterate and count through all combinations of good numbers less than each digit.

Input 'n' is zero or negative.

How to Handle:

Return 0 since a non-positive n indicates no valid integers can be formed.

Input 'n' is a single digit (0-9).

How to Handle:

Return n+1, as all digits from 0 to n are considered 'good'.

Input 'n' has repeating digits, such as 33 or 777.

How to Handle:

The algorithm must correctly handle these cases without double-counting.

Input 'n' contains digits not in the set {0, 1, 2, 5, 6, 8, 9}.

How to Handle:

The recursive/iterative function must skip over or adjust the bound properly when checking a disallowed digit.

Input 'n' is a large number that approaches integer limits.

How to Handle:

Ensure no integer overflow occurs during calculations or comparisons, potentially using long data types if needed.

n starts with an invalid digit (3,4,7).

How to Handle:

The starting digit must be converted to the next valid digit to continue processing (e.g., 3->5).

n consists entirely of 'good' digits (e.g., 111, 222, 555).

How to Handle:

The code counts these cases accurately as they are valid according to the definition.

All digits of 'n' are greater than 2, such as '9865'.

How to Handle:

The algorithm must iterate and count through all combinations of good numbers less than each digit.