C++ power of 2, regex, recursive, and iterative solutions


  • 0

    Solution 0: power of 2. If n contains alternating bits, then n+(n>>1) contains a contiguous chunk of 1s. For example 21=16+4+1=10101, and 21+(21>>1)=31=11111. 31+1=32=100000. And 32 is a power of 2, so return true.

    class Solution {
    public:
        bool hasAlternatingBits(int n) {
            n+=(n>>1)+1;
            return (n&(n-1))==0;
        }
    };
    

    Solution 1: regular expression ( C++ version of @2499370956's Java solution )

    class Solution {
    public:
        bool hasAlternatingBits(int n) {
            return regex_match(bitset<32>(n).to_string(),regex("(0)*(10)*1{0,1}"));
        }
    };
    

    Solution 2: recursion, keeping track of the last right-most bit

    class Solution {
    public:
        bool hasAlternatingBits(int n) {
            bool last=(n&1);
            return n==0 ? false : helper(n,!last);
        }
        
        bool helper(int n, bool last){
            return n==0 ? last==true : (n&1)==last ? false : helper(n>>1,!last);
        }
        
    };
    

    Solution 3: iterative loop

    class Solution {
    public:
        bool hasAlternatingBits(int n) {
            if (n==0) return false;
            bool last=n&1;
            while(n>>=1 > 0){
                if ((n&1)==last) return false;
                last=!last;
            }
            return true;
        }
    };
    
    class Solution {
    public:
        bool hasAlternatingBits(int n) {
            while(n){
                if ((n&1)==((n&2)>>1)) return false;
                n>>=1;
            }
            return true;
        }
    };
    

Log in to reply
 

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