Solution by rohitnandi12


  • 0
    R

    Primary Thoughts

    The Question is to reverse the binary string of a number n and return the decimal form of the reversed binary string e.g if n is 2 (0000 0000 0000 0000 0000 0000 0000 0010 ) the output should be 1073741824 (0100 0000 0000 0000 0000 0000 0000 0000).

    There are some trap holes in the question which are

    • In question it is mentioned 32 bit unsigned integer whose range is 0 to 232-1 ( 4294967295 ). The return type of the method is int and it cant hold that big range. In the current problem you can assume there wont be any integer input whose output will exceed the int range.
    • Sometimes we exclude the prefix zeros up to the first ON bit e.g 6 we represent as (110) and hence the output will be 3(011), which is wrong w.r.t to this question. Consider all the 32 bits.

    Test Cases

    Try to create your own test cases. You can take help of the interviewer, to validate your
    understanding of the problem.

    Test Inputs
    T1 : 48 // output : 201326592
    T2 : 56 // output : 469762048
    

    Approach #1 Using Library Function

    Algorithm

    • get the binary strings up to 32 bit (Integer.toBinaryString())
    • reverse the binary string (StringBuilder.reverse())
    • parse the binary string to a decimal number (Integer.parseInt(string,radix))

    Complexity Analysis

    • Time complexity : $$O(1)$$.

    • Space complexity : $$O(1)$$.


    Approach #2 Bit Wise Operators [Accepted]

    Algorithm

    • Initialize a result to 0
    • loop for 32 times
      • shift bits of result to left
      • if last bit of n is 1, add 1 to result
      • shift bits of n to right
    • return result

    Java

    public class Solution {
        // you need treat n as an unsigned value
        public int reverseBits(int n) {
    
            if(n==0)return 0;
    
            int result = 0;
            for(int i=0; i<32; i++){
                result = result<<1;
                if((n&1)==1)result+=1;
                n = n>>1;
            }
            return result;
        }
    }
    

    Complexity Analysis

    • Time complexity : $$O(1).

    • Space complexity : $$O(1)$$.

    Thank You for your up-vote. Happy Coding :-)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.