Solution of Bits

Approach #1

Try to swap each pair of bits once, and choose the maximum value. Complexity: O(log² N)

Approach #2

The maximum value can be obtained by swapping the first occurrence of a 0 bit with the last occurrence of a 1 bit. Complexity: O(log N).

Haskell implementation:

import Numeric (showIntAtBase, readInt)
import Data.Char (intToDigit, digitToInt)
import Data.List

bin x = showIntAtBase 2 intToDigit x ""
dec s = foldl' (\acc x -> acc * 2 + digitToInt x) 0 s

best x
    | not (elem '0' x)    = x
    | not (elem '1' x)    = x
    | firstZero > lastOne = x
    | otherwise           = front ++ "1" ++ middle ++ "0" ++ back
    where front     = take firstZero x
          middle    = take (lastOne-firstZero-1) (drop (firstZero+1) x)
          back      = drop (lastOne+1) x
          firstZero = head $ elemIndices '0' x
          lastOne   = last $ elemIndices '1' x

main = do
    input <- getContents
    let xs = map read $ words $ last $ lines input :: [Int]
    putStrLn $ concat $ intersperse " " $ map (show . dec . best . bin) xs