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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Number of Beautiful Integers in the Range

Difficulty: Hard

Problem Description

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].

Key Insights

  • A number can only be considered beautiful if it has an equal number of even and odd digits.
  • The divisibility condition by k must be checked for each number in the range.
  • The brute-force approach would involve checking each number individually, which may be inefficient for large ranges.
  • Efficiently counting even and odd digits can help in quickly determining the beauty of a number.

Space and Time Complexity

Time Complexity: O(n * d), where n is the number of integers in the range and d is the number of digits in each integer. Space Complexity: O(1), as we are using a fixed amount of space for counters and variables.

Solution

To solve the problem, we will iterate through each integer in the range [low, high]. For each integer, we will:

  1. Check if it is divisible by k.
  2. Count the even and odd digits.
  3. Determine if the counts of even and odd digits are equal.
  4. Increase a counter if both conditions are satisfied.

The algorithm uses simple arithmetic operations and a loop to check each number, making it straightforward yet potentially time-consuming for large ranges.

Code Solutions

def count_beautiful_integers(low, high, k):
    def is_beautiful(num):
        odd_count = 0
        even_count = 0
        for digit in str(num):
            if int(digit) % 2 == 0:
                even_count += 1
            else:
                odd_count += 1
        return odd_count == even_count

    beautiful_count = 0
    for num in range(low, high + 1):
        if num % k == 0 and is_beautiful(num):
            beautiful_count += 1
    return beautiful_count
← Back to All Questions