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
}

Leetcode. Single Number I, II, III

Single Number I

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Python (v1)
Time complexity: O(N)
Space complexity: O(1)


class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        xor = 0
        for n in nums:
            xor ^= n
        return xor

Python (v2)
Time complexity: O(N)
Space complexity: O(1)


from functools import reduce
class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        xor = reduce((lambda x, y: x ^ y), nums)
        return xor

 

Single Number II

Given an array of integers, every element appears three times except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Java (extra memory)
Time complexity: O(N)
Space complexity: O(1)

public class Solution {
    public int singleNumber(int[] A) {
        // write your code here
        if (A.length == 1){
            return A[0];
        }
        
        int[] bitCount = new int[32];
        for (int a : A){
            for (int i = 0; i < 32; ++i){
                boolean isSet = (a & (1 << i)) != 0; if (isSet){ bitCount[i] = (bitCount[i] + 1) % 3; } } } int res = 0; for (int i = 31; i >= 0; --i){
            res |= bitCount[i] << i;    
        }
        
        return res;
            
    }
}

Java
Time complexity: O(N)
Space complexity: O(1)

public class Solution {
    public int singleNumber(int[] A) {
        // write your code here
        int ones = 0;
        int twos = 0;
        for (int i = 0; i < nums.length; ++i){
            ones = (ones ^ nums[i]) & ~twos;
            twos = (twos ^ nums[i]) & ~ones;
        }
        return ones;            
    }
}

Java (extended to 4 times case)
Time complexity: O(N)
Space complexity: O(1)

public class Solution {
    public int singleNumber(int[] A) {
        int ones = 0;
        int twos = 0;

        for (int i = 0; i < nums.length; ++i){
            ones = (ones ^ nums[i]) & ~(twos & ones);
            twos = (twos ^ nums[i]) & ~ones & ~(twos & ones);
        }
        return ones;           
    }
}

 

Single Number III

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example:

Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

Note:

  1. The order of the result is not important. So in the above example, [5, 3] is also correct.
  2. Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

Java
Time complexity: O(N)
Space complexity: O(1)

public class Solution {
    public int[] singleNumber(int[] nums) {
        // write your code here
        int[] res = new int[2];
        
        if (nums == null || nums.length == 0){
            return res;
        }
        
        int diff = 0;
        
        for (int n : nums){
            diff ^= n;
        }
        
        diff &= ~(diff - 1);
        
        for (int n : nums){
            if ((n & diff) != 0){
                res[0] ^= n;
            } else {
                res[1] ^= n;    
            } 
        }
        
        return res;
           
    }
}