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.

This review may cover either or both challenges for this week.

I am sorry that the 'Try it' feature is currently working very slowly or not at all owing to some issue with my web hosting provider.

Try it 

Try running the script with any input:

Your $string =

example: 01010101010

⤡

#!/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