You are given a positive integer n.
We call an integer k fair if the number of even digits in k is equal to the number of odd digits in it.
Return the smallest fair integer that is greater than or equal to n.
Example 1:
Input: n = 2 Output: 10 Explanation: The smallest fair integer that is greater than or equal to 2 is 10. 10 is fair because it has an equal number of even and odd digits (one odd digit and one even digit).
Example 2:
Input: n = 403 Output: 1001 Explanation: The smallest fair integer that is greater than or equal to 403 is 1001. 1001 is fair because it has an equal number of even and odd digits (two odd digits and two even digits).
Constraints:
1 <= n <= 109Problem Overview: Given an integer n, return the smallest integer greater than or equal to n whose digits contain the same number of odd and even digits. Such numbers are called fair integers. The number of digits must therefore be even.
Approach 1: Brute Force Enumeration (O(k * d) time, O(1) space)
Start from n and increment the number until you encounter a fair integer. For each candidate, iterate through its digits and count how many are odd and how many are even. If the counts match, return the number immediately. Each validation costs O(d) where d is the digit length, and you may check up to k numbers before hitting a valid one. This approach relies on simple digit inspection using basic math operations and works well because fair integers appear frequently enough in the number space.
Approach 2: Case Discussion with Constructive Enumeration (O(k * d) time, O(1) space)
A key observation: a fair integer must have an even number of digits. If n has an odd digit length, no number of that length can be fair. The answer must therefore jump to the smallest fair number with the next even digit length. You can construct that minimum directly: place one leading 1, then as many 0 digits as possible (even digits), followed by the remaining 1s so the counts balance. For length L, the minimal fair number becomes "1" + "0" * (L/2) + "1" * (L/2 - 1).
If n already has an even digit length, simply enumerate upward from n. For each candidate, count odd and even digits and stop once they match. This combines enumeration with lightweight digit counting. Because the digit size is small (at most ~10 digits for typical constraints), the check is cheap and the first valid candidate usually appears quickly.
Recommended for interviews: Interviewers generally expect the case discussion approach. Recognizing that odd-length numbers cannot be fair avoids unnecessary checks and shows strong reasoning. Starting with brute force demonstrates correctness, while adding the digit-length insight and constructive jump to the next valid range shows deeper problem-solving skill.
We denote the number of digits of n as k, and the number of odd and even digits as a and b respectively.
a = b, then n itself is fair, and we can directly return n;k is odd, we can find the smallest fair number with k+1 digits, in the form of 10000111. If k is even, we can directly brute force closestFair(n+1).The time complexity is O(\sqrt{n} times log_{10} n).
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(k * d) | O(1) | Quick implementation when constraints are small and simple digit checks are acceptable. |
| Case Discussion + Enumeration | O(k * d) | O(1) | Preferred approach. Skips impossible odd-length ranges and may construct the smallest valid candidate directly. |
【每日一题】LeetCode 2417. Closest Fair Integer • Huifeng Guan • 248 views views
Watch 1 more video solutions →Practice Closest Fair Integer with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor