Return to Blog entry

O(log n) memory, O(log n) time algorithm Alexey Romanov 3rd November, 2008 14:25 (UTC)

Start with 1, double it and compare with n until you find a power of 2 greater than n. This is O(log n). Now you have the list of all powers of 2 which are less than n, so you can get the binary digits of n by the simple greedy algorithm. This is O(log n). If the last digit is 1, n is odd, otherwise n is even.

In Haskell:

powersOf2 n list@(x:xs)
             | n > x     = powersOf2 n (x*2 : list)
             | otherwise = list

reduce n [] = n reduce n (x:xs)
             | n >= x    = reduce (n - x) xs
             | otherwise = reduce n xs

isOdd n = reduce n (powersOf2 n [2]) == 1

Edit by Kirit: Edited to add formatting to source code

kirit.com