Closest Fair Integer - Practice Coding Problems

Closest Fair Integer - Problem

Math Enumeration Medium

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:

For n = 1, return 10 (1 even digit: 0, 1 odd digit: 1)
For n = 123, return 1230 (2 even digits: 2,0, 2 odd digits: 1,3)

Input & Output

Example 1 — Single Digit

$ Input: n = 1

› Output: 10

💡 Note: 1 has 1 odd digit (1) and 0 even digits, so it's not fair. The smallest fair number ≥ 1 is 10: 1 odd digit (1) and 1 even digit (0).

Example 2 — Already Fair

$ Input: n = 32

› Output: 32

💡 Note: 32 has 1 odd digit (3) and 1 even digit (2), so equal counts. It's already fair, return 32.

Example 3 — Need More Digits

$ Input: n = 123

› Output: 1023

💡 Note: 123 has 2 odd digits (1,3) and 1 even digit (2). Need equal counts. The next fair number is 1023: 2 odd digits (1,3) and 2 even digits (0,2).

Constraints

1 ≤ n ≤ 10⁹
n is a positive integer

Visualization

Tap to expand

Understanding the Visualization

Input

Given positive integer n = 123

Analyze

Count digits: 1(odd), 2(even), 3(odd) → 2 odd, 1 even

Find Fair

Next fair number: 1023 has 2 odd, 2 even digits

Key Takeaway

🎯 Key Insight: Fair numbers need equal counts of even and odd digits - build them systematically rather than checking every number

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is that fair numbers must have equal counts of even and odd digits. The brute force approach checks each number sequentially, while the optimized approach constructs fair number candidates systematically. Best approach is smart construction for better performance. Time: O(k×d) brute force, O(d²) optimized, Space: O(1) to O(d)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Iteration	O(k × d)	O(1)	Check every integer starting from n until we find a fair one
Smart Construction	O(d²)	O(d)	Construct fair numbers by analyzing digit patterns and building them systematically

Brute Force Iteration — Algorithm Steps

Step 1: Start with current number = n
Step 2: Count even and odd digits in current number
Step 3: If counts are equal, return current number
Step 4: Otherwise increment and repeat

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Begin checking from n

Count

Count even/odd digits in current number

Check

If equal counts, return; else increment

Code -

solution.c — C

#include <stdio.h>

void countEvenOdd(int num, int* evenCount, int* oddCount) {
    *evenCount = 0;
    *oddCount = 0;
    while (num > 0) {
        int digit = num % 10;
        if (digit % 2 == 0) {
            (*evenCount)++;
        } else {
            (*oddCount)++;
        }
        num /= 10;
    }
}

int solution(int n) {
    int current = n;
    while (1) {
        int evenCount, oddCount;
        countEvenOdd(current, &evenCount, &oddCount);
        if (evenCount == oddCount) {
            return current;
        }
        current++;
    }
}

int main() {
    int n;
    scanf("%d", &n);
    int result = solution(n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(k × d)

k is the difference between n and next fair number, d is digits per number to check

✓ Linear Growth

Space Complexity

O(1)

Only using a few variables to count digits

✓ Linear Space

12.4K Views

Medium Frequency

~25 min Avg. Time

234 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Iteration — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler