2417. Closest Fair Integer

MediumMathEnumeration
Leetcode Link

Problem Description

The problem asks for the smallest integer greater than or equal to a given positive integer n that is considered "fair." An integer is defined as "fair" if it has an equal number of even and odd digits. For example, if n is 23 which has one even and one odd digit, it is a fair integer. However, if n is 123, we should find the next integer where the count of even and odd digits is the same.

Intuition

The intuition behind solving this problem involves determining whether the given n itself is a fair number or not. If n is not fair, we need to find the next fair number after n.

Here's the thinking process for the solution:

  1. We first need to check if the given number of digits k in n is odd or even. If k is odd, there cannot be an equal number of even and odd digits in any number with k digits. In this case, we need to look for the smallest fair number with (k+1) digits (because the next fair number must have an even number of digits). This can be done by appending a '1' to the right half of the number made up of k number of '1's (to ensure the count of even and odd digits are the same) and padding the rest with zeroes.

  2. If k is even, we need to count the even and odd digits of n. If the count is already the same, n is the smallest fair number. If not, we need to increase n by 1 and re-evaluate until a fair number is found.

A recursive approach works here where we keep increasing n by 1 and checking if it is fair. If we come across an odd length of n while increasing it, we can directly return the smallest fair number with k+1 digits.

This algorithm works since every time we increment n, we move closer to the next fair number, and by handling the odd digit length directly, we avoid unnecessary checks.

Learn more about Math patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following is equvalent to O(3*2^n + n^3 + n!+ log n)?

Solution Approach

The given solution uses a simple iterative and recursive approach to find the smallest fair integer greater than or equal to the given number n. Here's how the Python code implements this approach:

  1. The closestFair method is a recursive function that takes an integer n as an argument.

  2. It starts by initializing three variables: a and b to count the number of odd and even digits respectively, and k to count the total number of digits.

  3. The method goes through each digit of n to calculate a, b, and k. This is done using a while loop which checks each digit by performing modulo and division operations: (t % 10) extracts the last digit of t and t //= 10 reduces t by one digit.

  4. If the last digit (t % 10) is odd (checked using bitwise AND with 1), a is incremented; otherwise, b is incremented.

  5. The variable k is incremented after each iteration to keep track of the number of digits processed.

  6. After the loop, if k is found to be odd, this means we cannot have a fair number with the same number of digits as n. Therefore, we calculate the smallest fair number with k+1 digits. This is done by creating a number with k+1 digits where the left half of the digits (excluding the middle digit) are all 1, ensuring equal even and odd digits, and the rest are 0. The number x represents 10^k (creating a new digit), and y represents a half of '1's. The expression '1' * (k >> 1) creates a string of ones half the length of k, and or '0' is used for cases when k >> 1 is zero.

  7. If k is even and a equals b, then n itself is a fair number so it is returned.

  8. Else, if n is not fair and k is even, the function calls itself recursively with the incremented value n + 1 and checks again.

Using recursion allows the algorithm to keep trying consecutive numbers after n until it discovers a fair number, and using the modulo and division operations enables it to easily count the even and odd digits in the integer. The direct calculation for the case when k is odd is a smart optimization that prevents unnecessary calculations by leveraging the fact that you can't have a fair number with an odd number of digits.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

Example Walkthrough

Let's say we are given n = 1234, and we wish to find the smallest fair integer greater than or equal to n.

Starting with n = 1234, the function initializes a and b to 0, and k would be the number of digits in n. We iterate through each digit to calculate the number of odd (a) and even (b) digits, as well as the total number of digits (k).

  1. 1234 - Last digit is 4 (even), so b becomes 1.
  2. 123 - Last digit is 3 (odd), so a becomes 1.
  3. 12 - Last digit is 2 (even), so b becomes 2.
  4. 1 - Last digit is 1 (odd), so a becomes 2.

After the loop, we can see that k = 4 (even number of total digits), and a = 2 and b = 2. This means the number of even and odd digits is the same (2 each), so n = 1234 is a fair number by the definition given in the problem description. Therefore, 1234 itself is the smallest fair integer greater than or equal to n, and we would return 1234.

Let’s look at another example with n = 123.

  1. 123 - Last digit is 3 (odd), so a becomes 1.
  2. 12 - Last digit is 2 (even), so b becomes 1.
  3. 1 - Last digit is 1 (odd), so a becomes 2.

Here, the loop finalizes with k = 3 (an odd number of total digits). Since we can't have a fair number with an odd number of digits, we need to find the smallest fair number with k+1 digits, which is 4.

Now, to get the smallest number with 4 digits, we take k = 3, and we need k + 1 = 4 digits in total. This is achieved by creating a number that has half of the digits as 1 and half as 0, ensuring the fair count of even and odd digits. The smallest such number is 1001, which has two '1's (odd digits) and two '0's (even digits).

In conclusion, if n = 1234, the smallest fair integer is 1234, and if n = 123, the smallest fair integer is 1001.

Solution Implementation

1class Solution:
2    def closestFair(self, num: int) -> int:
3        # Initialize digit counts for odds (odd_count) and evens (even_count)
4        # Also initialize the number of digits (num_digits)
5        odd_count = even_count = num_digits = 0
6        temp = num
7      
8        # Count the number of even and odd digits and the total digits in the number
9        while temp > 0:
10            digit = temp % 10
11            if digit % 2 == 1:
12                odd_count += 1
13            else:
14                even_count += 1
15            temp //= 10
16            num_digits += 1
17
18        # If the number of digits is odd, we find the smallest fair integer with more digits
19        if num_digits % 2 == 1:
20            base = 10 ** num_digits
21            half_odd_digits = '1' * (num_digits // 2)
22            if half_odd_digits == '':
23                half_odd_digits = '0'
24            return base + int(half_odd_digits)
25      
26        # If the number of odd and even digits is already the same, return the number
27        if odd_count == even_count:
28            return num
29      
30        # Otherwise recursively find the next closest fair number by incrementing the number
31        return self.closestFair(num + 1)
32
1class Solution {
2    // Method to find the closest 'fair' integer
3    public int closestFair(int n) {
4        // Initialize the count of odd and even digits
5        int countOdd = 0, countEven = 0;
6        // Variable to store the number of digits in n
7        int numDigits = 0;
8        // Copy of the original number n (temporary variable)
9        int temp = n;
10      
11        // Count the number of odd and even digits in n
12        while (temp > 0) {
13            // If the rightmost digit is odd
14            if ((temp % 10) % 2 == 1) {
15                countOdd++;
16            } else { // If the rightmost digit is even
17                countEven++;
18            }
19            temp /= 10; // Remove the rightmost digit of temp
20            numDigits++; // Increment the digit count
21        }
22      
23        // If the number of digits is odd, it's impossible to have an equal number of even and odd digits
24        if (numDigits % 2 == 1) {
25            // Find the smallest even digit number with one more digit than n
26            int nextPowerOfTen = (int) Math.pow(10, numDigits);
27            // Initialize the number which contains only '1' and half the length of the original number
28            int halfOnes = 0;
29            for (int i = 0; i < numDigits / 2; ++i) {
30                halfOnes = halfOnes * 10 + 1;
31            }
32            // Return the next 'fair' number which is fair (guaranteed by the next power of ten) 
33            // and has more digits than n
34            return nextPowerOfTen + halfOnes;
35        }
36      
37        // If n has an equal number of odd and even digits, it is fair so return n
38        if (countOdd == countEven) {
39            return n;
40        }
41      
42        // If n is not fair, recursively call the method with n + 1 to find the closest fair integer
43        return closestFair(n + 1);
44    }
45}
46
1#include <cmath> // include cmath for the pow function
2
3class Solution {
4public:
5    // Function to find the smallest integer greater than or equal to 'n'
6    // such that the count of even and odd digits is the same (a "fair" number)
7    int closestFair(int n) {
8        // 'oddDigits' counts odd digits, 'evenDigits' counts even digits
9        int oddDigits = 0, evenDigits = 0;
10        // 'temp' will be used to process the input number 'n'
11        int temp = n;
12        // 'numDigits' counts the number of digits in 'n'
13        int numDigits = 0;
14
15        // Loop to count even and odd digits in 'n'
16        while (temp > 0) {
17            if ((temp % 10) & 1) { // Check if the last digit is odd
18                ++oddDigits;
19            } else { // The last digit is even
20                ++evenDigits;
21            }
22            ++numDigits; // Increment the count of digits
23            temp /= 10; // Remove the last digit
24        }
25
26        // If the counts of even and odd digits are the same, return 'n'
27        if (oddDigits == evenDigits) {
28            return n;
29        }
30      
31        // If the number of digits is odd, it's impossible to have the same
32        // count of even and odd digits, so we calculate the next smallest "fair" number
33        if (numDigits % 2 == 1) {
34            // Calculate the smallest number with 'numDigits + 1' digits
35            int nextNumber = pow(10, numDigits);
36            // 'halfFair' will be the number with equal count of odd and even digits
37            int halfFair = 0;
38            // Calculate half of the required odd digits for a fair number
39            for (int i = 0; i < numDigits / 2; ++i) {
40                halfFair = halfFair * 10 + 1;
41            }
42            // Return the 'nextNumber' with 'halfFair' added to it (to make it fair)
43            return nextNumber + halfFair;
44        }
45
46        // If the number of digits is even but 'n' is not "fair", try the next integer
47        return closestFair(n + 1);
48    }
49};
50
1// Include the Math library for the Math.pow function
2function countDigits(num: number): number {
3    let count = 0;
4    while (num > 0) {
5        count++;
6        num = Math.trunc(num / 10);
7    }
8    return count;
9}
10
11function isFair(num: number): boolean {
12    let oddDigits = 0, evenDigits = 0;
13    let temp = num;
14
15    while (temp > 0) {
16        let digit = temp % 10;
17        if (digit % 2 === 0) {
18            evenDigits++;
19        } else {
20            oddDigits++;
21        }
22        temp = Math.trunc(temp / 10);
23    }
24
25    return oddDigits === evenDigits;
26}
27
28function nextFairNumber(num: number): number {
29    let digitCount = countDigits(num);
30
31    if (isFair(num)) {
32        return num;
33    }
34  
35    if (digitCount % 2 === 1) {
36        let nextNumber = Math.pow(10, digitCount);
37        let halfFairNumber = 0;
38        for (let i = 0; i < digitCount / 2; i++) {
39            halfFairNumber = halfFairNumber * 10 + 1;
40        }
41        return nextNumber + halfFairNumber;
42    }
43
44    return nextFairNumber(num + 1);
45}
46
47function closestFair(n: number): number {
48    return nextFairNumber(n);
49}
50
Not Sure What to Study? Take the 2-min Quiz：

Which data structure is used to implement priority queue?

Time and Space Complexity

The given Python code defines a method closestFair which finds the closest integer greater than or equal to n that contains an equal number of even and odd digits.

Time Complexity

Firstly, the method calculates the number of even (b) and odd (a) digits in the input integer n and counts the total number of digits (k). This involves a while loop that runs once for each digit in n, resulting in O(d) complexity, where d is the number of digits in n.

Next, for an odd number of digits (k), it constructs a number with a 1 repeated k >> 1 times (which takes constant time) and adds it to 10**k (also constant time). This part does not depend on the input size and is considered O(1).

If the number of even and odd digits is equal for an even number of digits (k), it immediately returns the number, which is O(1).

Lastly, if the number of even and odd digits is not equal, it recursively calls closestFair on the next integer n + 1. The worst-case scenario for this recursion is tricky to analyze, as it will depend on how the digits in n are distributed and how many increments are necessary to reach an integer with an equal number of even and odd digits. However, in the worst case, it could potentially increment through many numbers and hence have a worst-case time complexity affected by the magnitude of n and the mathematics of digit distribution, which is difficult to express in standard notation.

Space Complexity

The space complexity is primarily the space required to hold the variables and the recursion stack if the method keeps calling itself. Since the number of variables a, b, k, t, x, and y are fixed, the method utilizes O(1) space in terms of variables.

The recursion depth can be significant in the worst case (if the method keeps calling itself for each consecutive number until a fair number is found), but because Python's default recursion limit is typically a constant threshold (not dependent on the input size), the space complexity due to recursion is also O(1) under the Python recursion limit constraint.

In conclusion, the dominant time complexity is difficult to determine accurately without a more concrete analysis or pattern in the digit distribution of n. However, it can be bounded by O(d) for the initial digit-counting, and potentially worse, depending on subsequent recursive calls for an imbalanced n. The space complexity is O(1) under Python's recursion stack size constraint, as the recursion depth will hit a limit.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the running time of the following code?

1int sqrt(int n) {
2  for (int guess = 1; guess * guess <= n; guess++) {
3    if (guess * guess == n) {
4      return guess;
5    }
6  }
7  return -1;
8}

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫