LeetCode 2417 - Closest Fair Integer

In this problem, we are given a positive integer n, and we must find the smallest integer greater than or equal to n that is considered "fair". A number is fair when the count of even digits is exactly equal to the count of odd digits.

leetcodemediummathenumeration

LeetCode Problem 2417

Difficulty: 🟡 Medium
Topics: Math, Enumeration

Solution

Problem Understanding

In this problem, we are given a positive integer n, and we must find the smallest integer greater than or equal to n that is considered "fair".

A number is fair when the count of even digits is exactly equal to the count of odd digits. For example:

  • 10 is fair because it contains one even digit (0) and one odd digit (1)
  • 1234 is fair because it contains two odd digits (1, 3) and two even digits (2, 4)
  • 2221 is not fair because it contains three even digits and one odd digit

The task is not asking for all fair numbers, nor for the nearest fair number in absolute distance. We specifically need the smallest fair integer that is greater than or equal to n.

The constraints are relatively small:

  • 1 <= n <= 10^9

Since 10^9 has at most 10 digits, this immediately suggests that digit-based reasoning is feasible. We are not dealing with extremely large integers where sophisticated combinatorics or dynamic programming would be required.

An important observation is that a fair number must contain an even total number of digits. This is because the number of even digits must equal the number of odd digits. Therefore:

  • A 1-digit number can never be fair
  • A 3-digit number can never be fair
  • A 5-digit number can never be fair

Only numbers with an even digit count can possibly satisfy the condition.

Some edge cases are especially important:

  • Very small numbers like 1 or 2, where the answer must jump to a 2-digit number
  • Numbers with an odd number of digits, because no number of that same length can be fair
  • Numbers that are already fair, where we should immediately return the number itself
  • Large values near 10^9, where the next fair number may require increasing the digit length

Approaches

Brute Force Approach

The simplest possible strategy is to start at n and increment one number at a time until we find a fair integer.

For each number:

  1. Convert it to a string
  2. Count how many digits are even
  3. Count how many digits are odd
  4. Check whether the counts are equal

As soon as we find such a number, we return it.

This approach is straightforward and always correct because we examine every candidate in increasing order. The first valid fair integer we encounter must therefore be the smallest one greater than or equal to n.

However, this method can become inefficient when there are large gaps between fair numbers. For example, if n has an odd number of digits, we may waste time checking many impossible candidates before reaching a number with an even digit count.

Optimal Approach

The key insight is that the input constraints are small enough that we do not actually need advanced digit DP or combinatorial construction.

Instead, we can optimize the brute force approach slightly by leveraging one critical property:

A fair number must have an even number of digits.

This means:

  • If the current candidate has an odd digit count, we can immediately jump to the next power of 10
  • We only need to test numbers with even digit lengths

Since numbers up to 10^9 contain at most 10 digits, the search space is manageable.

The algorithm becomes:

  1. Start from n
  2. If the number of digits is odd:
  • Jump directly to the smallest number with the next digit length
  1. Otherwise:
  • Check whether the number is fair
  • If not, increment and continue

This pruning dramatically reduces unnecessary checks.

Approach Time Complexity Space Complexity Notes
Brute Force O(k × d) O(1) Checks every number one by one
Optimal O(k × d) O(1) Skips impossible odd-length ranges

Here:

  • k is the number of checked candidates
  • d is the number of digits, at most 10

Algorithm Walkthrough

  1. Initialize a variable current with the value n.
  2. Enter an infinite loop because we are guaranteed that a fair number eventually exists.
  3. Convert current to a string and determine its digit count.
  4. If the digit count is odd, no number with this digit length can ever be fair. Therefore:

  • Jump directly to the next power of 10

  • For example:

  • 999 becomes 1000

  • 12345 becomes 100000

  1. If the digit count is even:
  • Count how many digits are even
  • Count how many digits are odd
  1. If the two counts are equal:
  • Return current
  • Since we are searching in increasing order, this is the smallest valid answer
  1. Otherwise:
  • Increment current by 1
  • Continue the loop

Why it works

The algorithm examines candidate numbers in strictly increasing order. Any skipped ranges contain numbers with odd digit lengths, and such numbers can never be fair because equal counts of even and odd digits require an even total digit count.

Therefore, the first fair number encountered must be the smallest fair integer greater than or equal to n.

Python Solution

class Solution:
    def closestFair(self, n: int) -> int:
        current = n

        while True:
            digits = str(current)

            # Fair numbers must have an even number of digits
            if len(digits) % 2 == 1:
                current = 10 ** len(digits)
                continue

            even_count = 0

            for ch in digits:
                if int(ch) % 2 == 0:
                    even_count += 1

            odd_count = len(digits) - even_count

            if even_count == odd_count:
                return current

            current += 1

The implementation closely follows the algorithm described earlier.

We begin with current = n and repeatedly test candidate numbers.

The first optimization checks whether the number of digits is odd. If so, we immediately jump to the next power of 10 because no odd-length number can be fair.

For even-length numbers, we iterate through every digit and count how many are even. Since the total digit count is already known, the odd digit count can be computed as:

odd_count = len(digits) - even_count

If the counts match, we return the number immediately.

Otherwise, we increment the candidate and continue searching.

Because the maximum number of digits is very small, this solution is efficient enough for the constraints.

Go Solution

func closestFair(n int) int {
	current := n

	for {
		digits := []rune(string(runeSlice(current)))

		// Fair numbers must have even digit counts
		if len(digits)%2 == 1 {
			current = powerOf10(len(digits))
			continue
		}

		evenCount := 0

		for _, ch := range digits {
			digit := int(ch - '0')

			if digit%2 == 0 {
				evenCount++
			}
		}

		oddCount := len(digits) - evenCount

		if evenCount == oddCount {
			return current
		}

		current++
	}
}

func runeSlice(num int) []rune {
	return []rune(fmt.Sprintf("%d", num))
}

func powerOf10(exp int) int {
	result := 1

	for i := 0; i < exp; i++ {
		result *= 10
	}

	return result
}

A cleaner and more typical LeetCode Go implementation would avoid helper conversions through rune slices and instead use strconv.Itoa. Here is the preferred version:

import "strconv"

func closestFair(n int) int {
	current := n

	for {
		digits := strconv.Itoa(current)

		if len(digits)%2 == 1 {
			current = 1

			for i := 0; i < len(digits); i++ {
				current *= 10
			}

			continue
		}

		evenCount := 0

		for _, ch := range digits {
			digit := int(ch - '0')

			if digit%2 == 0 {
				evenCount++
			}
		}

		if evenCount*2 == len(digits) {
			return current
		}

		current++
	}
}

The Go implementation mirrors the Python logic almost exactly.

The main language-specific difference is digit conversion. In Python, converting a number to a string and iterating through characters is very concise. In Go, we use strconv.Itoa to convert integers into strings.

Another small difference is that Go does not provide exponentiation for integers directly, so we manually compute powers of 10 using a loop.

Worked Examples

Example 1

Input:

n = 2

Initial state:

Current Digits Length Action
2 "2" 1 Odd length, jump

Since 1-digit numbers cannot be fair:

current = 10

Now check 10:

Digit Type
1 Odd
0 Even

Counts:

Even Odd
1 1

The counts are equal, so:

Answer = 10

Example 2

Input:

n = 403

Initial state:

Current Length Action
403 3 Odd length, jump

Jump to:

current = 1000

Now analyze 1000:

Digit Type
1 Odd
0 Even
0 Even
0 Even

Counts:

Even Odd
3 1

Not fair, increment.

Next candidate:

1001

Digit analysis:

Digit Type
1 Odd
0 Even
0 Even
1 Odd

Counts:

Even Odd
2 2

This number is fair.

Answer = 1001

Complexity Analysis

Measure Complexity Explanation
Time O(k × d) We examine k candidates, each requiring digit traversal
Space O(1) Only a few variables are used

The digit count d is at most 10 because n <= 10^9.

The practical runtime is very fast because the optimization skips entire ranges of impossible odd-length numbers. Although the theoretical bound depends on how many candidates are checked, the actual search space is small enough for all valid inputs.

Test Cases

sol = Solution()

assert sol.closestFair(2) == 10        # Smallest possible input range
assert sol.closestFair(403) == 1001    # Must jump to next digit length
assert sol.closestFair(10) == 10       # Already fair
assert sol.closestFair(11) == 12       # Next fair number
assert sol.closestFair(1000) == 1001   # Close fair number
assert sol.closestFair(999) == 1001    # Odd digit count jump
assert sol.closestFair(1234) == 1234   # Already balanced
assert sol.closestFair(2222) == 2231   # Requires several increments
assert sol.closestFair(99999999) == 1000000011  # Large transition
assert sol.closestFair(1) == 10        # Single digit edge case
Test Why
n = 2 Smallest non-fair starting value
n = 403 Requires skipping odd digit length
n = 10 Input already fair
n = 11 Immediate next valid number
n = 1000 Nearby fair number exists
n = 999 Jump across digit boundary
n = 1234 Balanced even/odd digits
n = 2222 Multiple increments needed
n = 99999999 Large-number behavior
n = 1 Smallest possible input

Edge Cases

Single-Digit Inputs

Single-digit numbers can never be fair because they contain either one even digit or one odd digit, never both equally. A naive implementation might waste time checking all single-digit values individually.

This implementation handles the case efficiently by detecting that the digit count is odd and immediately jumping to the next power of 10.

Numbers With Odd Digit Lengths

Any number with an odd number of digits is automatically invalid. For example:

  • 100
  • 12345
  • 9999999

A buggy implementation might continue checking these numbers one by one even though none can ever be fair.

This solution skips entire impossible ranges by jumping directly to the smallest number with the next digit length.

Inputs Already Fair

Some inputs already satisfy the condition. Examples include:

  • 10
  • 1234
  • 1001

An incorrect implementation might accidentally increment before checking the current number and therefore miss the optimal answer.

This implementation always checks the current value before incrementing, ensuring the smallest valid number is returned.