Sponsored
Sponsored
To form the maximum odd binary number from a given binary string, observe that the binary number should have '1' at the end to be odd. Among the remaining bits, arrange as many '1's as possible at the leading positions while maintaining the '1' at the end. This approach involves counting the occurrences of '1' and '0', then constructing the number.
Time Complexity: O(n), where n is the length of the string as it needs one pass to count and another to construct.
Space Complexity: O(1) for the counting variables.
#include <string>
using namespace std;
string maxOddBinaryNumber(const string &s) {
int ones = 0, zeros = 0;
for (char c : s) {
if (c == '1')
ones++;
else
zeros++;
}
string result(ones - 1, '1');
result.append(string(zeros, '0'));
result += '1';
return result;
}
int main() {
string s = "0101";
cout << maxOddBinaryNumber(s) << endl;
return 0;
}This solution uses string manipulation, counting the number of '1's and '0's. It constructs a new string with maximum leading '1's and a trailing '1' to ensure oddness.
A different approach involves sorting the binary string while ensuring a '1' is at the end. To maximize the binary number, the initial part of the string should consist of leading '1's followed by '0's, then append a single '1' at the end to turn the number odd.
Time Complexity: O(n log n) for sorting.
Space Complexity: O(1) assuming sorting in place is allowed.
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5// Comparator function for qsort
6int compare(const void *a, const void *b) {
7 return (*(char *)b - *(char *)a);
8}
9
10void maxOddBinaryNumber(char *s) {
11 int length = strlen(s);
12 qsort(s, length, sizeof(char), compare);
13 for (int i = length - 1; i >= 0; i--) {
14 if (s[i] == '1') {
15 // Move last '1' to the end
16 for (int j = i; j < length - 1; j++)
17 s[j] = s[j + 1];
18 s[length - 1] = '1';
19 break;
20 }
21 }
22 printf("%s\n", s);
23}
24
25int main() {
26 char s[] = "0101";
27 maxOddBinaryNumber(s);
28 return 0;
29}This solution sorts the string in descending order and ensures '1' is moved to the last position. Sorting places '1's before '0's. The trailing '1' ensures oddness.
Solve with full IDE support and test cases