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

Closest Fair Integer

Number: 2560

Difficulty: Medium

Paid? Yes

Companies: N/A

Problem Description

Given a positive integer n, find the smallest fair integer that is greater than or equal to n. An integer is defined as fair if the count of even digits is equal to the count of odd digits.

Key Insights

  • A fair integer must have an even total number of digits.
  • If n has an odd number of digits, the search should start from the smallest number with an even digit count.
  • A brute-force iteration checking each number works since the maximum value is 10^9.
  • Efficient digit counting can be done by iterating over the string representation or via numerical operations.

Space and Time Complexity

Time Complexity: O((m - n) * D) where m is the fair integer found and D is the number of digits in the candidate number. Space Complexity: O(1)

Solution

The solution employs a brute-force approach starting at n and incrementing until a fair integer is found. A helper function is used to count even and odd digits in each candidate. If n has an odd number of digits, it is adjusted to the smallest number with an even digit count (for example, from 99 to 100). This ensures that only numbers with an even number of digits are considered, since only they can potentially be fair. The algorithm continues checking sequentially, with an extra check to adjust when the number of digits changes from even to odd.

Code Solutions

# Function to check if a given number is fair
def is_fair(num):
    even_count, odd_count = 0, 0
    for digit in str(num):
        if int(digit) % 2 == 0:
            even_count += 1
        else:
            odd_count += 1
    return even_count == odd_count

def closest_fair_integer(n):
    # If n has an odd number of digits, skip to the smallest even-digit number.
    if len(str(n)) % 2 == 1:
        n = 10 ** len(str(n))
    # Increment until a fair integer is found.
    while not is_fair(n):
        n += 1
        # If the number of digits becomes odd (e.g., 99 -> 100), jump to next even-digit number.
        if len(str(n)) % 2 == 1:
            n = 10 ** len(str(n))
    return n

# Example usage:
print(closest_fair_integer(403))  # Expected output: 1001
← Back to All Questions