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.

Description Hints 2 Solution Video 14:10

2417. Closest Fair Integer

Medium43.7% acceptancePremium elsewhere, free here

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 <= 10⁹

Topics

Enumeration Math

Hints open one at a time

Hint 1

Suppose that the number that we are looking for has the same number of digits as n, the answer, in this case, will not be very far from n, so you can do a simple brute force. Can you prove why this is true?

Hint 2

How do you handle the case when the resulting number has more digits than n?

14:10

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

Your code is saved on this device.Solution