Maximum Odd Binary Number - Practice Coding Problems

Maximum Odd Binary Number - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: s = "010"

› Output: "001"

💡 Note: We have one '1' and two '0s. To maximize and keep odd: place 0 '1's at front (since 1-1=0), two '0's in middle, and one '1' at end → "001"

Example 2 — Multiple 1s

$ Input: s = "101"

› Output: "101"

💡 Note: We have two '1's and one '0'. Place 1 '1' at front, one '0' in middle, one '1' at end → "101". This is already optimal.

Example 3 — Many 1s

$ Input: s = "1111"

› Output: "1111"

💡 Note: All bits are '1'. Place 3 '1's at front, no '0's in middle, one '1' at end → "1111". Already maximum odd number.

Constraints

1 ≤ s.length ≤ 100
s consists only of '0' and '1'
s contains at least one '1'

Visualization

Tap to expand

Understanding the Visualization

Input

Binary string with mixed 1s and 0s

Process

Rearrange to maximize while keeping odd

Output

Maximum possible odd binary number

Key Takeaway

🎯 Key Insight: Place all 1s at front for maximum value, except keep one 1 at end to ensure odd

Asked in

G Google 25 a Amazon 20 M Microsoft 15

The key insight is that for maximum odd number, we need all 1s at the front (for maximum value) except one 1 at the end (to ensure odd). Best approach is greedy construction: count bits and arrange optimally. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Generate All Permutations	O(n!)	O(n!)	Generate all possible arrangements and find maximum odd number
Greedy Construction	O(n)	O(1)	Count 1s and 0s, then construct maximum odd number optimally

Generate All Permutations — Algorithm Steps

Generate all permutations of the binary string
Filter permutations that end with '1' (odd numbers)
Convert each to integer and find maximum
Return the maximum as string

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate All

Create all possible permutations

Filter Odd

Keep only those ending with '1'

Find Max

Select lexicographically largest

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void swap(char* a, char* b) {
    char temp = *a;
    *a = *b;
    *b = temp;
}

void permute(char* str, int left, int right, char* maxOdd) {
    if (left == right) {
        if (str[right] == '1') {
            if (strlen(maxOdd) == 0 || strcmp(str, maxOdd) > 0) {
                strcpy(maxOdd, str);
            }
        }
    } else {
        for (int i = left; i <= right; i++) {
            swap(&str[left], &str[i]);
            permute(str, left + 1, right, maxOdd);
            swap(&str[left], &str[i]);
        }
    }
}

char* solution(char* s) {
    int n = strlen(s);
    char* result = (char*)malloc((n + 1) * sizeof(char));
    result[0] = '\0';
    
    char* temp = (char*)malloc((n + 1) * sizeof(char));
    strcpy(temp, s);
    
    permute(temp, 0, n - 1, result);
    
    free(temp);
    return result;
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    char* result = solution(s);
    printf("%s\n", result);
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n!)

Generating all permutations takes factorial time

⚠ Quadratic Growth

Space Complexity

O(n!)

Storing all permutations requires factorial space

⚠ Quadratic Space

32.0K Views

Medium Frequency

~15 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Generate All Permutations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler