Spotify Puzzles. Reversed Binary Numbers (Difficulty Level: Easy)

Yi has moved to Sweden and now goes to school here. The first years of schooling she got in China, and the curricula do not match completely in the two countries. Yi likes mathematics, but now… The teacher explains the algorithm for subtraction on the board, and Yi is bored. Maybe it is possible to perform the same calculations on the numbers corresponding to the reversed binary representations of the numbers on the board? Yi dreams away and starts constructing a program that reverses the binary representation, in her mind. As soon as the lecture ends, she will go home and write it on her computer. See Spotify Puzzles.

Task

Your task will be to write a program for reversing numbers in binary. For instance, the binary representation of 13 is 1101, and reversing it gives 1011, which corresponds to number 11.

Input

The input contains a single line with an integer N, 1 ≤ N ≤ 1000000000.

Output

Output one line with one integer, the number we get by reversing the binary representation of N.

Sample input 1
13
Sample output 1
11
Sample input 2
47
Sample output 2
61
Java
Time complexity: O(1)
Space complexity: O(1)

public class Solution {
    //full integer range is supported
    public static int reverseBits(int n) {

        if (n == 0) return 0;

        int result = 0;

        while (n != 0) {
            result = (result << 1) + (n & 1); 
            n >>>= 1;
        }

        return result;
    }
}
Go
Time complexity: O(1)
Space complexity: O(1)

package main

import (
	"fmt"
)

func reverseBits(n int) int{
	if n == 0 {
		return 0
	}
	
	res := 0
	for n != 0 {
	        res <<= 1 
            if n & 1 == 1{ 
                res += 1 
            } 
            n >>= 1
	}
	return res
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s