2417. Closest Fair Integer
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:
-
We first need to check if the given number of digits
k
inn
is odd or even. Ifk
is odd, there cannot be an equal number of even and odd digits in any number withk
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 ofk
number of '1's (to ensure the count of even and odd digits are the same) and padding the rest with zeroes. -
If
k
is even, we need to count the even and odd digits ofn
. If the count is already the same,n
is the smallest fair number. If not, we need to increasen
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.
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:
-
The
closestFair
method is a recursive function that takes an integern
as an argument. -
It starts by initializing three variables:
a
andb
to count the number of odd and even digits respectively, andk
to count the total number of digits. -
The method goes through each digit of
n
to calculatea
,b
, andk
. This is done using awhile
loop which checks each digit by performing modulo and division operations:(t % 10)
extracts the last digit oft
andt //= 10
reducest
by one digit. -
If the last digit (
t % 10
) is odd (checked using bitwise AND with1
),a
is incremented; otherwise,b
is incremented. -
The variable
k
is incremented after each iteration to keep track of the number of digits processed. -
After the loop, if
k
is found to be odd, this means we cannot have a fair number with the same number of digits asn
. Therefore, we calculate the smallest fair number withk+1
digits. This is done by creating a number withk+1
digits where the left half of the digits (excluding the middle digit) are all1
, ensuring equal even and odd digits, and the rest are0
. The numberx
represents10^k
(creating a new digit), andy
represents a half of '1's. The expression'1' * (k >> 1)
creates a string of ones half the length ofk
, andor '0'
is used for cases whenk >> 1
is zero. -
If
k
is even anda
equalsb
, thenn
itself is a fair number so it is returned. -
Else, if
n
is not fair andk
is even, the function calls itself recursively with the incremented valuen + 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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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
).
1234
- Last digit is4
(even), sob
becomes1
.123
- Last digit is3
(odd), soa
becomes1
.12
- Last digit is2
(even), sob
becomes2
.1
- Last digit is1
(odd), soa
becomes2
.
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
.
123
- Last digit is3
(odd), soa
becomes1
.12
- Last digit is2
(even), sob
becomes1
.1
- Last digit is1
(odd), soa
becomes2
.
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
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.
Which algorithm is best for finding the shortest distance between two points in an unweighted graph?
Recommended Readings
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 Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
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