Problem

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 _thesmallest fair integer that is greater than or equal to _n.

Examples

Example 1:

1
2
3
4

    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:

1
2
3
4

    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 odd and even digits (two odd digits and two even digits).

Constraints:

  • 1 <= n <= 10^9

Solution

Method 1 – Brute Force Enumeration

Intuition

A fair integer has an equal number of even and odd digits. Since the constraint is small, we can check each number starting from n and return the first fair integer we find.

Approach

  1. Start from n and increment by 1 each time.
  2. For each number, count the number of even and odd digits.
  3. If the counts are equal, return the number.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    int closestFair(int n) {
        for (int x = n; ; ++x) {
            int even = 0, odd = 0, t = x;
            while (t) {
                if ((t % 10) % 2 == 0) even++;
                else odd++;
                t /= 10;
            }
            if (even == odd) return x;
        }
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

func closestFair(n int) int {
    for x := n; ; x++ {
        even, odd, t := 0, 0, x
        for t > 0 {
            if (t%10)%2 == 0 {
                even++
            } else {
                odd++
            }
            t /= 10
        }
        if even == odd {
            return x
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    public int closestFair(int n) {
        for (int x = n; ; x++) {
            int even = 0, odd = 0, t = x;
            while (t > 0) {
                if ((t % 10) % 2 == 0) even++;
                else odd++;
                t /= 10;
            }
            if (even == odd) return x;
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    fun closestFair(n: Int): Int {
        var x = n
        while (true) {
            var even = 0; var odd = 0; var t = x
            while (t > 0) {
                if ((t % 10) % 2 == 0) even++ else odd++
                t /= 10
            }
            if (even == odd) return x
            x++
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def closestFair(self, n: int) -> int:
        x = n
        while True:
            even = odd = 0
            t = x
            while t > 0:
                if (t % 10) % 2 == 0:
                    even += 1
                else:
                    odd += 1
                t //= 10
            if even == odd:
                return x
            x += 1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

impl Solution {
    pub fn closest_fair(n: i32) -> i32 {
        let mut x = n;
        loop {
            let mut even = 0;
            let mut odd = 0;
            let mut t = x;
            while t > 0 {
                if (t % 10) % 2 == 0 {
                    even += 1;
                } else {
                    odd += 1;
                }
                t /= 10;
            }
            if even == odd {
                return x;
            }
            x += 1;
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    closestFair(n: number): number {
        let x = n;
        while (true) {
            let even = 0, odd = 0, t = x;
            while (t > 0) {
                if ((t % 10) % 2 === 0) even++;
                else odd++;
                t = Math.floor(t / 10);
            }
            if (even === odd) return x;
            x++;
        }
    }
}

Complexity

  • ⏰ Time complexity: O(k * m), where k is the answer minus n, and m is the number of digits in each number checked.
  • 🧺 Space complexity: O(1)