/**

 Given a positive integer, check whether it has alternating bits: namely, if two adjacent bits will always have different values.

 Example 1:
 Input: 5
 Output: True
 Explanation:
 The binary representation of 5 is: 101

 Example 2:
 Input: 7
 Output: False
 Explanation:
 The binary representation of 7 is: 111.

 Example 3:
 Input: 11
 Output: False
 Explanation:
 The binary representation of 11 is: 1011.

 Example 4:
 Input: 10
 Output: True
 Explanation:
 The binary representation of 10 is: 1010.

 */
public class Binary_Number_with_Alternating_Bits {

    public static void main (String[] args) {
        Binary_Number_with_Alternating_Bits out = new Binary_Number_with_Alternating_Bits();
        Solution s = out.new Solution();

        System.out.println(s.hasAlternatingBits(3)); // 11
        System.out.println(s.hasAlternatingBits(4)); // 100
        System.out.println(s.hasAlternatingBits(5)); // 101
    }

    class Solution {
        public boolean hasAlternatingBits(int n) {

            if (n <= 0) {
                return false;
            }

            int prev = n & 1; // true => 1, false => 0
            n >>= 1;

            while (n > 0) {

                if (prev == (n & 1)) {
                    return false;
                }

                prev = n & 1;
                n >>= 1;
            }

            return true;
        }
    }
}

############

class Solution {
    public boolean hasAlternatingBits(int n) {
        n ^= (n >> 1);
        return (n & (n + 1)) == 0;
    }
}

// OJ: https://leetcode.com/problems/binary-number-with-alternating-bits/
// Time: O(1)
// Space: O(1)
class Solution {
public:
    bool hasAlternatingBits(int n) {
        int prev = -1;
        while (n) {
            int d = n % 2;
            n /= 2;
            if (prev == d) return false;
            prev = d;
        }
        return true;
    }
};

class Solution:
    def hasAlternatingBits(self, n: int) -> bool:
        n ^= n >> 1
        return (n & (n + 1)) == 0

############

In [1]: bin(5)
Out[1]: '0b101'

func hasAlternatingBits(n int) bool {
	n ^= (n >> 1)
	return (n & (n + 1)) == 0
}

impl Solution {
    pub fn has_alternating_bits(n: i32) -> bool {
        let t = n ^ (n >> 1);
        (t & (t + 1)) == 0
    }
}

class Solution {
    public boolean hasAlternatingBits(int n) {
        if (n <= 2)
            return true;
        else if (n <= 4)
            return false;
        int prevBit = n & 1;
        n >>= 1;
        while (n > 0) {
            int curBit = n & 1;
            if (prevBit == curBit)
                return false;
            prevBit = curBit;
            n >>= 1;
        }
        return true;
    }
}

############

class Solution {
    public boolean hasAlternatingBits(int n) {
        n ^= (n >> 1);
        return (n & (n + 1)) == 0;
    }
}

// OJ: https://leetcode.com/problems/binary-number-with-alternating-bits/
// Time: O(1)
// Space: O(1)
class Solution {
public:
    bool hasAlternatingBits(int n) {
        int prev = -1;
        while (n) {
            int d = n % 2;
            n /= 2;
            if (prev == d) return false;
            prev = d;
        }
        return true;
    }
};

class Solution:
    def hasAlternatingBits(self, n: int) -> bool:
        n ^= n >> 1
        return (n & (n + 1)) == 0

############

In [1]: bin(5)
Out[1]: '0b101'

func hasAlternatingBits(n int) bool {
	n ^= (n >> 1)
	return (n & (n + 1)) == 0
}

impl Solution {
    pub fn has_alternating_bits(n: i32) -> bool {
        let t = n ^ (n >> 1);
        (t & (t + 1)) == 0
    }
}

693 - Binary Number with Alternating Bits

All Problems

All Solutions

Welcome to Subscribe On Youtube

All Problems

All Solutions