Flipping Bits HackerRank

Problem Link:

https://www.hackerrank.com/challenges/flipping-bits/problem

Solution:

 class Result {

    public static long flippingBits(long n) {

       

        long n1=~n;

        String s=Long.toBinaryString(n1);

        //System.out.println(s);

        double res=0.0;

        for(int i=0;i<32;i++){

            if(s.charAt(63-i)=='1'){

                res=res+Math.pow(2,i);

            }

        }

        

        return (long)res;

    }

}

Time Complexity:O(logn) ie more than O(1) and about O(log(2^31-1))(max value as n can be

2^31-1). Actually when we call this function then it will find out its binary and at

the instant of time maximum recursive calls will be logn. So that's why its time complexity

will be O(logn).

Space Complexity:O(1)

Auxillary Space:O(1)

Approach:

1. First we will find out the negation of number.

2. Here First we will convert the negated number to binary value using the

Long.toBinaryString() function.

3. Then we will traverse the string and if we get set bit then we will find out value Math.pow(2, i)

and add it in one variable, which we return later.

We follow this approach because we need to flip all the bits which can be done

by using ~ operator and for that only first we negated number and find out its binary value.

Moreover, we ran a loop from LSB to MSB in a manner to find out Math.pow(2, index) and

add it in the result variable.

Usage of 63-i is because long is a 64-bit number while constraint of n is up to 32 bits.

{ Now question then why don't we use Integer.toBinaryString() function directly instead

Long.toBinaryString() .

The answer is because the given function parameter is of long data type.

That's why we counted only the last 32 bits by using 63-i which will range

from 63rd index to 31st index in the binary string.

}

----------------------------------------------------------------------------------

"Thanks For Reading.😇"

"Share Further To Increase Knowledge Treasure.😊"