Greedy: Maximum odd binary number

Coding Interview Questions

1 min read

Problem Statement:

You are given a string, that has atleast one.

Re-arrange the bits so that the number is the odd binary number and is the maximum number.

Example:

Input: s = '0110'
Output: '1001'

Solution Explanation:

A binary number is odd if the last digit is 1.

To get the max number, add the max num of 1 in the left side and then all 0 and then a final 1 at the end of the string.

Time Complexity: O(1)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


string solution(string s) 
{
    int count1 = count(s.begin(), s.end(), '1');
    int count0 = s.length() - count1;

    return std::string(count1 - 1, '1') + std::string(count0, '0') + "1";
}

int main() 
{
    string str = "0110";

    cout << solution(str) << "\n";

    return 0;
}