Number of Beautiful Integers in the Range

Hard

Asked by:

8 views

Topics:

Dynamic Programming

You are given positive integers low, high, and k.

A number is beautiful if it meets both of the following conditions:

The count of even digits in the number is equal to the count of odd digits.
The number is divisible by k.

Return the number of beautiful integers in the range [low, high].

Example 1:

Input: low = 10, high = 20, k = 3
Output: 2
Explanation: There are 2 beautiful integers in the given range: [12,18]. 
- 12 is beautiful because it contains 1 odd digit and 1 even digit, and is divisible by k = 3.
- 18 is beautiful because it contains 1 odd digit and 1 even digit, and is divisible by k = 3.
Additionally we can see that:
- 16 is not beautiful because it is not divisible by k = 3.
- 15 is not beautiful because it does not contain equal counts even and odd digits.
It can be shown that there are only 2 beautiful integers in the given range.

Example 2:

Input: low = 1, high = 10, k = 1
Output: 1
Explanation: There is 1 beautiful integer in the given range: [10].
- 10 is beautiful because it contains 1 odd digit and 1 even digit, and is divisible by k = 1.
It can be shown that there is only 1 beautiful integer in the given range.

Example 3:

Input: low = 5, high = 5, k = 2
Output: 0
Explanation: There are 0 beautiful integers in the given range.
- 5 is not beautiful because it is not divisible by k = 2 and it does not contain equal even and odd digits.

Constraints:

0 < low <= high <= 10⁹
0 < k <= 20

Try coding it in LeetCode

Number of Beautiful Integers in the Range

Hard

Asked by:

8 views

Topics:

Dynamic Programming

You are given positive integers low, high, and k.

A number is beautiful if it meets both of the following conditions:

The count of even digits in the number is equal to the count of odd digits.
The number is divisible by k.

Return the number of beautiful integers in the range [low, high].

Example 1:

Input: low = 10, high = 20, k = 3
Output: 2
Explanation: There are 2 beautiful integers in the given range: [12,18]. 
- 12 is beautiful because it contains 1 odd digit and 1 even digit, and is divisible by k = 3.
- 18 is beautiful because it contains 1 odd digit and 1 even digit, and is divisible by k = 3.
Additionally we can see that:
- 16 is not beautiful because it is not divisible by k = 3.
- 15 is not beautiful because it does not contain equal counts even and odd digits.
It can be shown that there are only 2 beautiful integers in the given range.

Example 2:

Input: low = 1, high = 10, k = 1
Output: 1
Explanation: There is 1 beautiful integer in the given range: [10].
- 10 is beautiful because it contains 1 odd digit and 1 even digit, and is divisible by k = 1.
It can be shown that there is only 1 beautiful integer in the given range.

Example 3:

Input: low = 5, high = 5, k = 2
Output: 0
Explanation: There are 0 beautiful integers in the given range.
- 5 is not beautiful because it is not divisible by k = 2 and it does not contain equal even and odd digits.

Constraints:

0 < low <= high <= 10⁹
0 < k <= 20

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 bounds for the range (low and high), and what is the maximum possible value for low and high? Should I assume they are positive integers?
What defines a 'beautiful' integer? Can you please provide a more formal definition, especially regarding divisibility and the count of even/odd digits, including how to handle the digit '0'?
If no beautiful integers exist within the given range, what should the function return?
Are there any specific performance expectations, or are there memory limitations I should be aware of, given the potentially large range of numbers?
Should I treat the input values (low and high) as inclusive or exclusive bounds when searching for beautiful integers?

Brute Force Solution

Approach

The brute force approach is all about checking every single number within the given range. We'll go through each number one by one and see if it meets the criteria to be considered 'beautiful'.

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

Start with the first number in the provided range.
Check if the current number is 'beautiful' according to the rules (e.g., does it have an even number of digits, and is it divisible by some number?).
If the number is 'beautiful', make a note of it.
Move on to the next number in the range.
Repeat steps two through four until you've checked all the numbers up to the end of the range.
Count how many numbers you noted as 'beautiful'. That's the final answer.

Code Implementation

def number_of_beautiful_integers_brute_force(low_range, high_range, divisible_by):
    beautiful_integer_count = 0

    for current_number in range(low_range, high_range + 1):
        number_as_string = str(current_number)
        number_of_digits = len(number_as_string)

        # Check if the number has an even number of digits
        if number_of_digits % 2 == 0:

            # Check if the number is divisible by the given number
            if current_number % divisible_by == 0:
                # Increment the count of beautiful integers
                beautiful_integer_count += 1

    return beautiful_integer_count

Big(O) Analysis

Time Complexity

O(R) – The brute force approach iterates through every number in the given range, from 'low' to 'high'. Let R be the size of the range (high - low + 1). For each number in the range, it performs a check to determine if it's 'beautiful'. This check involves a fixed set of operations. The outer loop iterates R times, and the beauty check takes constant time, therefore the time complexity is dominated by the range traversal, resulting in O(R).

Space Complexity

O(1) – The brute force approach, as described, iterates through the input range and checks each number individually. The algorithm only needs to keep track of a single counter for 'beautiful' numbers. Since there are no auxiliary data structures or recursion involved, the space used remains constant regardless of the input range size. Therefore, the space complexity is O(1).

Optimal Solution

Approach

The most efficient way to count beautiful numbers involves breaking down the problem into smaller, manageable parts. We use a technique similar to counting within certain constraints to avoid checking every number. This allows us to use a principle similar to building blocks where we make smarter decisions along the way.

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

First, figure out what makes a number "beautiful" based on the rules.
Instead of checking every number from the start to the end of the range, find the count of beautiful numbers up to the end, and then subtract the count of beautiful numbers up to the start. This gives you the count within the range.
To count beautiful numbers up to any number, break that number into individual digits.
Work through the digits from left to right, building beautiful numbers step-by-step. Think of it like creating a decision tree: at each digit position, you choose possible values for the digit and see how it affects the beautiful number condition.
When choosing a digit, consider two cases: One, the digit is strictly smaller than the digit at that position in the original number; Two, the digit is exactly the same as the digit in the original number. The first case lets you easily count possibilities because any digit combination after that will work. The second case forces you to continue comparing digit by digit.
Use previous calculations to avoid redundant work. Store calculated values so you don't have to recompute them when you encounter the same situation again. This is the 'building blocks' strategy.
Handle edge cases carefully. For example, numbers starting with zero might not be beautiful. Also, make sure your calculations respect the condition of the problem.

Code Implementation

def number_of_beautiful_integers(
    low_range, high_range, divisible_by
):
    def count_beautiful_up_to(number):
        number_string = str(number)
        number_length = len(number_string)

        memo = {}

        def dp(index, even_count, is_tight):
            if index == number_length:
                if even_count * 2 == number_length:
                    return 1
                else:
                    return 0

            key = (index, even_count, is_tight)
            if key in memo:
                return memo[key]

            count = 0
            upper_bound = (
                int(number_string[index]) if is_tight else 9
            )

            for digit in range(upper_bound + 1):
                new_even_count = (
                    even_count + 1 if digit % 2 == 0 else even_count
                )
                new_is_tight = (
                    is_tight and digit == int(number_string[index])
                )
                count += dp(index + 1, new_even_count, new_is_tight)

            memo[key] = count
            return count

        return dp(0, 0, True)

    high_count = count_beautiful_up_to(high_range)

    # Adjust low_range to exclude it if it's not beautiful.
    low_count = count_beautiful_up_to(low_range - 1)

    # Subtract the counts to find the number in the specified range.
    return high_count - low_count

def is_beautiful(number, divisible_by):
    number_string = str(number)
    number_length = len(number_string)
    even_digits = 0

    for digit_char in number_string:
        digit = int(digit_char)
        if digit % 2 == 0:
            even_digits += 1

    # Check if the number of even digits is half the total digits
    if even_digits * 2 != number_length:
        return False

    return number % divisible_by == 0

Big(O) Analysis

Time Complexity

O(n*k*k) – The algorithm iterates through the digits of the input number, which has length 'n'. For each digit, it explores possibilities for 'k' possible values (0-9). A memoization table, of size related to the count of even and odd digits, is used. The dimension of this table is proportional to k*k. So the total runtime is O(n*k*k) where n is the number of digits in the input numbers and k is the number of possible digit values (0-9).

Space Complexity

O(N*K) – The primary space complexity arises from memoization (step 6), where previously calculated values are stored to avoid redundant computations. We need to store the results of subproblems, and the size of this storage depends on the number of digits in the upper bound of the range, let's call it N, and the possible states related to the beauty conditions (even/odd count difference and other parameters), denoted as K. Thus, we would be storing intermediate results in a data structure (like a multi-dimensional array or hash map) of size proportional to N*K, where N is the number of digits in the input number, and K represents the state of building the beautiful number. Therefore, the auxiliary space complexity is O(N*K).

Edge Cases

Case	How to Handle
low > high	Return 0, as the range is invalid.
k is zero	Return 0, because an integer cannot be divisible by 0.
low and high are equal	Check if the single number is beautiful and return 1 or 0 accordingly.
low is a very small number and high is a very large number	The digit DP algorithm should handle large ranges efficiently, and test the limits of integer overflow.
low and high are negative numbers	Since the problem defines beautiful integers as positive numbers with a count of even digits equal to odd digits and being divisible by k, negative numbers are not beautiful. Treat as empty range
k is larger than the largest possible beautiful number within the range.	Handle by always returning 0 when the number is divisible by k is impossible within the range.
Integer overflow during digit DP calculations.	Use appropriate data types (e.g., long long) to prevent integer overflows.
No beautiful numbers exist within the range	The DP algorithm correctly counts zero beautiful numbers; simply return 0.