We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Beautiful Integers in the Range

Number: 3017

Difficulty: Hard

Paid? No

Companies: Apple, Infosys

Problem Description

Given a range [low, high] and an integer k, count the numbers in the range that are "beautiful". A number is beautiful if:

  • It has an equal number of even and odd digits.
  • It is divisible by k. Return the total count of beautiful numbers in the range.

Key Insights

  • Only numbers with an even number of digits can possibly have an equal count of even and odd digits.
  • The problem constraints (high up to 10^9) imply that numbers have at most 10 digits.
  • A digit dynamic programming (DP) approach can be used with state parameters that keep track of:
    • The current position in the digit string.
    • Whether the prefix is tightly matching the limit (tight flag).
    • Whether we have started the number (to handle leading zeros).
    • The count of digits used so far.
    • The balance (difference) between even and odd digit counts.
    • The current modulo k value.
  • Use DP to count valid numbers in [0, X] and then use inclusion-exclusion (count(high) - count(low-1)).

Space and Time Complexity

Time Complexity: O(L * 2 * 2 * (L+1) * (2L+1) * k) where L is the maximum number of digits (at most 10) and k ≤ 20. Space Complexity: O(L * 2 * 2 * (L+1) * (2L+1) * k) for the DP memoization.

Solution

We solve the problem using a digit DP approach. First, convert the limit (either high or low-1) into its digit representation. Then, use recursion with memoization maintaining the following state:

  • pos: current index in the digit array.
  • tight: indicates whether the current digit choices are bound by the given number’s prefix.
  • started: indicates whether we have started the number (to bypass leading zero issues).
  • countUsed: the number of digits that have been placed.
  • balance: the difference between the count of even and odd digits (increasing by 1 for even, decreasing by 1 for odd).
  • modVal: the current number modulo k. At the end of the digit array (pos equals length of the number), we verify that a number has been started, the total number of digits is even (ensuring equal counts are possible), the balance is zero, and modVal is 0.

Finally, compute the answer as count(high) - count(low - 1). This approach effectively counts valid numbers up to a limit using digit DP with extra state parameters.

Code Solutions

class Solution:
    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:
        # Helper function to count valid numbers <= limit
        def count(limit):
            s = str(limit)
            n = len(s)
            from functools import lru_cache

            @lru_cache(maxsize=None)
            def dp(pos, tight, started, countUsed, balance, modVal):
                # Base case: if we processed all digits
                if pos == n:
                    # Check: must have started, have an even number of digits, zero balance and 0 mod
                    if started and countUsed % 2 == 0 and balance == 0 and modVal == 0 and countUsed > 0:
                        return 1
                    return 0
                total = 0
                upper = int(s[pos]) if tight else 9
                for digit in range(0, upper+1):
                    new_tight = tight and (digit == upper)
                    new_started = started or (digit != 0)
                    new_countUsed = countUsed
                    new_balance = balance
                    new_modVal = modVal
                    if new_started:
                        new_countUsed += 1
                        # Update balance: even digit adds +1, odd digit subtracts 1.
                        if digit % 2 == 0:
                            new_balance += 1
                        else:
                            new_balance -= 1
                        new_modVal = (modVal * 10 + digit) % k
                    total += dp(pos+1, new_tight, new_started, new_countUsed, new_balance, new_modVal)
                return total

            return dp(0, True, False, 0, 0, 0)

        return count(high) - count(low - 1)

# Example usage:
# sol = Solution()
# print(sol.numberOfBeautifulIntegers(10, 20, 3))
← Back to All Questions