Problem Link : 2864. Maximum Odd Binary Number [LeetCode]
Problem Level : Easy
Topics : Math String Greedy
Time: O(n)
Space: O(1)
Problem Description : 2864. Maximum Odd Binary Number
You are given a binary string s that contains at least one '1'.
You have to rearrange the bits in such a way that the resulting binary number is the maximum odd binary number that can be created from this combination.
Return a string representing the maximum odd binary number that can be created from the given combination.
Note that the resulting string can have leading zeros.
Example 1:
Input: s = "010" Output: "001" Explanation: Because there is just one '1', it must be in the last position. So the answer is "001".
Example 2:
Input: s = "0101" Output: "1001" Explanation: One of the '1's must be in the last position. The maximum number that can be made with the remaining digits is "100". So the answer is "1001".
Constraints:
1 <= s.length <= 100sconsists only of'0'and'1'.scontains at least one'1'.
Solution :
Approach:
- Count the number of ‘1’s (
ones) and ‘0’s (zeros) in the given binary string. - Construct the maximum odd binary number by placing ‘1’s, followed by ‘0’s, and ending with ‘1’.
- Ensure the number of ‘1’s is reduced by one to maintain oddness.
- Return the resulting binary string.
- Count the number of ‘1’s (
Code :
class Solution {
public: string maximumOddBinaryNumber(string s) {
int zeros = ranges::count(s, ‘0’);
int ones = s.length() – zeros;
return string(ones – 1, ‘1’) + string(zeros, ‘0’) + ‘1’;
}
};
class Solution:
def maximumOddBinaryNumber(self, s: str) -> str:
return ‘1’ * (s.count(‘1’) – 1) + ‘0’ * s.count(‘0’) + ‘1’
Output :
Input: s = “010”
Output: “001”
