Problem Description

You need to find the smallest "fair" integer that is greater than or equal to a given positive integer n.

A "fair" integer is defined as an integer where the count of even digits (0, 2, 4, 6, 8) equals the count of odd digits (1, 3, 5, 7, 9).

For example:

• 1234 is fair because it has 2 even digits (2, 4) and 2 odd digits (1, 3)
• 123 is not fair because it has 1 even digit (2) and 2 odd digits (1, 3)
• 10 is fair because it has 1 even digit (0) and 1 odd digit (1)

Given a positive integer n, you need to return the smallest fair integer that is greater than or equal to n. If n itself is fair, return n.

The solution uses a recursive approach with case analysis:

• First, it counts the number of odd digits (a) and even digits (b) in n, along with the total number of digits (k)
• If n has an odd number of total digits, the next fair number will have k+1 digits (even number of digits), constructed in a specific pattern
• If n has an even number of total digits and is already fair (a == b), return n
• Otherwise, recursively check n+1 until a fair number is found

Intuition

The key insight is that fair numbers must have an even total number of digits. Why? Because we need equal counts of odd and even digits - if we have x odd digits and x even digits, the total is 2x, which is always even.

This leads us to consider two main cases:

1. When n has an even number of digits: We can check if n is already fair. If it is, we're done. If not, we can try incrementing n by 1 and checking again. Since the number of digits remains even (until we overflow to the next digit count), we have a good chance of finding a fair number nearby.

2. When n has an odd number of digits: No number with an odd digit count can be fair. So we need to jump to the smallest number with k+1 digits (where k is the current digit count).

   For example, if n = 999 (3 digits), we need to find the smallest 4-digit fair number. The smallest such number would be 1000 plus some adjustment to make it fair. Since we need 2 odd digits and 2 even digits, and 1000 already has 1 odd digit (1) and 3 even digits (0,0,0), we need to convert some zeros to odd digits. The smallest way is to make the last digits odd, giving us 1011.

   The pattern for the smallest fair number with an even number of digits k is: start with 10...0 (k digits), then make the last k/2 - 1 digits into 1s. This gives us exactly k/2 odd digits and k/2 even digits.

The recursive approach naturally handles the transition: when we can't find a fair number with the current digit count, we either increment and try again (for even digit counts) or jump to the next digit count (for odd digit counts).

Learn more about Math patterns.

Solution Approach

The implementation follows a recursive approach with case-based logic:

Step 1: Count digits and their types

a = b = k = 0
t = n
while t:
    if (t % 10) & 1:
        a += 1  # count odd digits
    else:
        b += 1  # count even digits
    t //= 10
    k += 1      # total digit count

We iterate through each digit of n using modulo 10 and integer division. The expression (t % 10) & 1 checks if a digit is odd (bitwise AND with 1 returns 1 for odd numbers, 0 for even).

Step 2: Handle odd digit count

if k & 1:
    x = 10**k
    y = int('1' * (k >> 1) or '0')
    return x + y

When k is odd (checked using k & 1), we construct the smallest fair number with k+1 digits:

• x = 10**k gives us the smallest (k+1)-digit number (e.g., 1000 for k=3)
• y = int('1' * (k >> 1) or '0') creates a number with k/2 ones (using right shift k >> 1 for integer division)
• For example, if k=3, we get x=1000 and y=1, resulting in 1001 (2 odd digits: 1,1 and 2 even digits: 0,0)

Step 3: Handle even digit count

if a == b:
    return n
return self.closestFair(n + 1)

When k is even:

• If a == b, then n is already fair, so we return it
• Otherwise, we recursively check n+1 until we find a fair number

The recursive call self.closestFair(n + 1) continues the search. This works because:

• If n+1 still has an even number of digits, we check if it's fair
• If n+1 overflows to an odd number of digits, the algorithm will jump to the next even digit count

This approach efficiently handles all cases without needing to check every single number, especially when jumping from odd to even digit counts.

Example Walkthrough

Let's trace through the algorithm with n = 99:

Step 1: Count digits and their types

• Processing 99:
  • First digit (9): odd, so a = 1
  • Second digit (9): odd, so a = 2
  • Total: a = 2 (odd digits), b = 0 (even digits), k = 2 (total digits)

Step 2: Check if k is odd

• k = 2, which is even (2 & 1 = 0), so we skip the odd digit count handling

Step 3: Check if n is fair

• a = 2, b = 0, so a ≠ b
• 99 is not fair, so we recursively call with n + 1 = 100

Recursive call with n = 100:

• Count digits: 1 (odd), 0 (even), 0 (even)
• a = 1, b = 2, k = 3
• k = 3 is odd (3 & 1 = 1), so we construct the next fair number:
  • x = 10^3 = 1000 (smallest 4-digit number)
  • y = int('1' * (3 >> 1)) = int('1' * 1) = 1
  • Return 1000 + 1 = 1001

Verification: 1001 has digits 1, 0, 0, 1

• Odd digits: 1, 1 (count = 2)
• Even digits: 0, 0 (count = 2)
• 2 = 2, so 1001 is fair ✓

Let's trace one more example with n = 1234:

Step 1: Count digits

• Processing 1234: 1 (odd), 2 (even), 3 (odd), 4 (even)
• a = 2, b = 2, k = 4

Step 2: Check if k is odd

• k = 4 is even, so we continue to step 3

Step 3: Check if n is fair

• a = 2, b = 2, so a = b
• 1234 is already fair, return 1234

The algorithm efficiently handles both cases: when we need to jump to the next even digit count (as with 99 → 1001), and when the number is already fair (as with 1234).

Solution Implementation

Time and Space Complexity

Time Complexity: O(√n × log₁₀ n)

The algorithm recursively increments n until it finds a "fair" number (equal count of odd and even digits). In the worst case, when starting from a number with even digit count where odd and even digit counts are unbalanced, the function will recursively call itself multiple times.

• Each recursive call performs O(log₁₀ n) operations to count the digits and determine odd/even digit counts
• The maximum number of recursive calls is bounded by O(√n) because:
  • When the number has odd digit count k, the function immediately returns a constructed fair number without recursion
  • When the number has even digit count, it needs to find the next fair number by incrementing
  • The gap between consecutive fair numbers with even digit count can be at most O(√n) in the worst case

Therefore, the overall time complexity is O(√n × log₁₀ n).

Space Complexity: O(√n)

The space complexity is dominated by the recursion stack depth. Since the function can make up to O(√n) recursive calls in the worst case before finding a fair number, and each recursive call uses O(1) additional space for local variables (a, b, k, t), the total space complexity is O(√n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Stack Overflow from Deep Recursion

The recursive approach can cause stack overflow when the input number has many digits and is far from a fair number. For example, if n = 999999, the algorithm needs to recursively call itself thousands of times to reach 1000011.

Solution: Convert to an iterative approach or add a recursion depth limit:

def closestFair(self, n: int) -> int:
    while True:
        # Count digits logic
        odd_count = even_count = total_digits = 0
        temp_n = n

        while temp_n > 0:
            digit = temp_n % 10
            if digit & 1:
                odd_count += 1
            else:
                even_count += 1
            temp_n //= 10
            total_digits += 1

        # Handle odd digit count
        if total_digits & 1:
            next_power_of_10 = 10 ** total_digits
            half_digits = total_digits >> 1
            ones_to_add = int('1' * half_digits) if half_digits > 0 else 0
            return next_power_of_10 + ones_to_add

        # Check if fair
        if odd_count == even_count:
            return n

        n += 1  # Iterate instead of recurse

2. Integer Overflow for Large Numbers

When dealing with very large numbers, 10 ** total_digits might exceed integer limits in some languages (though Python handles arbitrary precision integers).

Solution: Be mindful of language-specific integer limits and consider using appropriate data types or libraries for large number handling.

3. Inefficient Incremental Search

When the current number has even digits but isn't fair, incrementing by 1 repeatedly can be inefficient. For instance, going from 9999 to 10001 requires checking 2 unnecessary numbers.

Solution: Implement smarter jumping logic:

def closestFair(self, n: int) -> int:
    while True:
        # ... digit counting logic ...

        if total_digits & 1:
            # Jump directly to next even-digit count
            return 10 ** total_digits + int('1' * (total_digits >> 1) if total_digits >> 1 else '0')

        if odd_count == even_count:
            return n

        # Smart increment: if close to power of 10, jump directly
        if n >= 10 ** total_digits - 10:
            n = 10 ** total_digits
        else:
            n += 1

4. Edge Case with Zero

The handling of half_digits = 0 case (when total_digits = 1) needs careful attention. The expression int('1' * 0) would fail without the or '0' fallback.

Solution: Always handle the edge case explicitly:

if half_digits > 0:
    ones_to_add = int('1' * half_digits)
else:
    ones_to_add = 0