Max odd binary

You are given a binary string that has at least one ‘1’. Write a script to rearrange the bits in such a way that the resulting binary number is the maximum odd binary number and return the resulting binary string. The resulting string can have leading zeros.

Examples

Example 1
Input: $str = '1011'
Output: '1101'
'1101' is max odd binary (13).

Example 2
Input: $str = '100'
Output: '001'
'001' is max odd binary (1).

Example 3
Input: $str = '111000'
Output: '110001'

Example 4
Input: $str = '0101'
Output: '1001'

Example 5
Input: $str = '1111'
Output: '1111'

Analysis

If the input string contains $u 1s and $z 0s then the answer is:

'1' x ($u - 1) . '0' x $z . '1'

In words, that's all the 1s except one, followed by all the 0s, followed by one 1.

The final 1 is to make the answer odd. All the other 1s are pushed as far left as possible to maximise the size of the result.

The post features a very well thought out, extensive solution in Perl that uses string multiplication to create the largest odd binary number. He gives us a lin2dec utility that helps validate his solutions. He also provides an excellent explanation of the underlying mathematical principles behind the task he has undertaken.

Try it 

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

use v5.26;    # The Weekly Challenge - 2026-03-30
use utf8;     # Week 367 - task 1 - Max odd binary
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';
use Encode;

max_odd_binary('000111');
max_odd_binary('100');
max_odd_binary('111000');
max_odd_binary('1111');
max_odd_binary('0101');
max_odd_binary('0000');

sub max_odd_binary {
    
    my ($string, $ones, $zeroes, $result);
    
    # initialise
    $string = $_[0];
    say qq[\nInput:  $string = ] . bin2dec($string);
    
    # count ones and zeroes
    $ones = $string =~ s|1|1|g;
    $zeroes = $string =~ s|0|0|g;
    
    unless ($ones) {
        say qq[Output: impossible - no 1s];
        return;
    }
    
    # make result
    $result = '1' x ($ones - 1) . '0' x $zeroes . '1';
    
    say qq[Output: $result = ] . bin2dec($result);
}

sub bin2dec {
    
    # converts binary string to decimal
    my $result = 0;
    $result = 2 * $result + $_ for split('', $_[0]);
    return $result;
}

15 lines of code

Output from script

Input:  000111 = 7
Output: 110001 = 49

Input:  100 = 4
Output: 001 = 1

Input:  111000 = 56
Output: 110001 = 49

Input:  1111 = 15
Output: 1111 = 15

Input:  0101 = 5
Output: 1001 = 9

Input:  0000 = 0
Output: impossible - no 1s