Two ways, one good, one bad


  • 0
    V

    Explanation:
    Just try to build the given number yourself, and at each position, flip whether the digit is 0 or 1. That would mean, you need to know which one to start with. That is easy to find. Just check if the given number is even or not, if even, then the last bit should be 0, so your start will be 0

    Example:
    0_1507685986877_Capture.PNG

    public bool HasAlternatingBits(int n) {
            int start = n%2 == 0 ? 0 :1; // if n is even, then last bit is 0, otherwise 1
            long num = 0; long it = 1; //it == iterator. 
            while(num < n){
                num += start * it;
                it *= 2;
                start = start == 0 ? 1: 0; //flip the start
            }
            return num == n;
        }
    

    The reason the above code is inefficient is that for large numbers especially with repeated bits at the end like 10101010101010101010101010100 (357913940 decimal), it won't take advantage of that or for that matter for bits repeated at the front. It just builds the number with alternationg bits and checks if you can build that number or not.

    Another way is using bits. See, the following code

         public bool HasAlternatingBits(int n) {
                int x = n & 1; //get the last bit
                n = n >> 1; //get the remaining number
                while(n != 0) {
                    if(x == (n & 1)) { //every time check if the current bit is equal to last one
                        return false;
                    }
                    x = n & 1; //update the last bit
                    n = n >> 1;
                }
                return true; // if not, return true
            }
    

Log in to reply
 

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