You are given N positive integers.
For every integer, you can choose to either swap two bits in its binary representation, or do nothing.
Your task is to compute the maximum integer that can be obtained from every given value.
The first line of input contains N.
The second line of input contains N space-separated integers.
The only line of output should contain all N maximum values that can be obtained, separated by spaces.
- 1 ≤ N ≤ 1000
- 0 ≤ any number < 231
1 5 6 9
|1 6 6 12|
Try to swap each pair of bits once, and choose the maximum value. Complexity: O(log2 N)
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).
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