Skip to main content
Talentd

Closest Fair Integer - Solution & Explanation

MediumPremiumFree on FleetCodeMathEnumeration6 min read
Practice this problem

Problem Statement

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 <= 109

Approach Overview

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

Solution

We denote the number of digits of n as k, and the number of odd and even digits as a and b respectively.

  • If a = b, then n itself is fair, and we can directly return n;
  • Otherwise, if 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).

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force EnumerationO(k * d)O(1)Quick implementation when constraints are small and simple digit checks are acceptable.
Case Discussion + EnumerationO(k * d)O(1)Preferred approach. Skips impossible odd-length ranges and may construct the smallest valid candidate directly.

Video Solution

2417. Closest Fair Integer (Leetcode Medium) • Programming Live with Larry • 196 views views

Frequently Asked Questions

Is Closest Fair Integer easy or hard?
Closest Fair Integer is typically rated Medium. The implementation is straightforward, but recognizing that fair numbers must have an even digit count and handling the edge case when n has odd length requires careful reasoning.
Closest Fair Integer Python/Java solution
In Python or Java, repeatedly check numbers starting from n. Convert the number to digits (string conversion or modulo operations), count odd and even digits, and return the first number where the counts match. The logic is identical across Python, Java, C++, and Go.
How to solve Closest Fair Integer in O(n)?
Treat the problem as enumeration over integers starting from n. For each candidate, extract digits using modulo and division operations and count odd and even digits. Stop once both counts are equal. Adding a rule to skip odd digit lengths significantly reduces the search space.
What is the best approach for Closest Fair Integer?
The most practical approach is case-based enumeration. First check the digit length of n. If it is odd, jump directly to the smallest fair integer with the next even length. If it is even, iterate upward from n and count odd and even digits until they match. This keeps the implementation simple while avoiding unnecessary checks.
Is Closest Fair Integer asked at Google/Amazon/Meta?
Problems involving digit properties, enumeration, and mathematical observations frequently appear in interviews at companies like Google and Amazon. While this exact question may vary, the underlying technique of digit counting and pruning impossible cases is commonly tested.
What data structure is used in Closest Fair Integer?
No complex data structure is required. The solution mainly uses integer arithmetic and simple counters to track odd and even digits. This makes it primarily a math and enumeration problem rather than a data-structure-heavy one.
What is the time complexity of Closest Fair Integer?
The typical solution runs in O(k * d) time where d is the number of digits and k is the number of integers checked before finding a fair one. Each check scans the digits once to count odd and even digits. Space complexity is O(1) since only a few counters are used.

Ready to solve this problem?

Practice Closest Fair Integer with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Two Numbers

Next

Reverse Integer