Check if a number has bits in alternate pattern | Set 1

Given an integer n > 0, the task is to find whether this integer has an alternate pattern in its bits representation. For example- 5 has an alternate pattern i.e. 101. 
Print "Yes" if it has an alternate pattern otherwise "No". Here alternate patterns can be like 0101 or 1010.

Examples: 

Input : 15
Output : No
Explanation: Binary representation of 15 is 1111.

Input : 10
Output : Yes
Explanation: Binary representation of 10 is 1010.

A naive approach to check if a number has bits in alternate patterns:

A simple approach is to find its binary equivalent and then check its bits.  

// C++ program to find if a number has alternate bit pattern #include <bits/stdc++.h> using namespace std; // Returns true if n has alternate bit pattern else false bool findPattern(int n) {  // Store last bit  int prev = n % 2;  n = n / 2;  // Traverse through remaining bits  while (n > 0) {  int curr = n % 2;  // If current bit is same as previous  if (curr == prev)  return false;  prev = curr;  n = n / 2;  }  return true; } // Driver code int main() {  int n = 10;  if (findPattern(n))  cout << "Yes";  else  cout << "No";  return 0; } // This code is contributed by Sania Kumari Gupta (kriSania804) 

// C program to find if a number has alternate bit pattern #include <stdbool.h> #include <stdio.h> // Returns true if n has alternate bit pattern else false bool findPattern(int n) {  // Store last bit  int prev = n % 2;  n = n / 2;  // Traverse through remaining bits  while (n > 0) {  int curr = n % 2;  // If current bit is same as previous  if (curr == prev)  return false;  prev = curr;  n = n / 2;  }  return true; } // Driver code int main() {  int n = 10;  if (findPattern(n))  printf("Yes");  else  printf("No");  return 0; } // This code is contributed by Sania Kumari Gupta // (kriSania804) 

// Java program to find if a number has alternate bit // pattern class Test {  // Returns true if n has alternate bit pattern  // else false  static boolean findPattern(int n)  {  // Store last bit  int prev = n % 2;  n = n / 2;  // Traverse through remaining bits  while (n > 0) {  int curr = n % 2;  // If current bit is same as previous  if (curr == prev)  return false;  prev = curr;  n = n / 2;  }  return true;  }  // Driver method  public static void main(String args[])  {  int n = 10;  System.out.println(findPattern(n) ? "Yes" : "No");  } } // This code is contributed by Sania Kumari Gupta // (kriSania804) 

# Python3 program to find if a number  # has alternate bit pattern # Returns true if n has alternate  # bit pattern else false def findPattern(n): # Store last bit prev = n % 2 n = n // 2 # Traverse through remaining bits while (n > 0): curr = n % 2 # If current bit is same as previous if (curr == prev): return False prev = curr n = n // 2 return True # Driver code n = 10 print("Yes") if(findPattern(n)) else print("No") # This code is contributed by Anant Agarwal. 

// Program to find if a number // has alternate bit pattern using System; class Test {  // Returns true if n has alternate  // bit pattern else returns false  static bool findPattern(int n)  {  // Store last bit  int prev = n % 2;  n = n / 2;  // Traverse through remaining bits  while (n > 0) {  int curr = n % 2;  // If current bit is same as previous  if (curr == prev)  return false;  prev = curr;  n = n / 2;  }  return true;  }  // Driver method  public static void Main()  {  int n = 10;  Console.WriteLine(findPattern(n) ? "Yes" : "No");  } } // This code is contributed by Anant Agarwal. 

<script> // Javascript program to find if a number // has alternate bit pattern // Returns true if n has alternate // bit pattern else false function findPattern(n) {    // Store last bit  let prev = n % 2;  n = Math.floor(n / 2);  // Traverse through remaining bits  while (n > 0)  {  let curr = n % 2;  // If current bit is   // same as previous  if (curr == prev)  return false;  prev = curr;  n = Math.floor(n / 2);  }  return true; } // Driver code let n = 10; if (findPattern(n))  document.write("Yes"); else  document.write("No");   // This code is contributed by gfgking </script> 

Yes

Time Complexity: O(log₂n)
Auxiliary Space: O(1)

An efficient approach to check if a number has bits in alternate patterns:

1) Right shift the number by 1 (x = n >> 1) so that all 1s become aligned with all 0s for an alternate bit pattern number.
2) Now do an XOR of x with n (y = x ^ n). This will have a number with all 1s. Note that XOR of two bits is 0 when they are same, otherwise 1.
3) Now we mainly need to check if all bits are set or not. To check this, we simply check if y & (y+1) is 0 or not.

#include <iostream> using namespace std; // Returns true if n has alternate bit pattern else false bool findPattern(int n) {  if (n <= 1) return false; int x = n >> 1;  int y = x ^ n;  return (y & (y+1)) == 0; } // Driver code int main() { int n = 10; // equal to 10101 if (findPattern(n)) cout << "Yes" << endl; else cout << "No" << endl; return 0; } 

// C program to find if a number has alternate bit pattern #include <stdbool.h> #include <stdio.h> // Returns 1 if n has alternate bit pattern else 0 bool findPattern(int n) {  if (n <= 1) return false;  int x = n >> 1;  int y = x ^ n;  return (y & (y+1)) == 0; } // Driver code int main() {  int n = 10; // equal to 10101  if (findPattern(n))  printf("Yes");  else  printf("No");  return 0; } // This code is contributed by "Madhukar Sharma" 

public class Solution {  // Returns 1 if n has alternate bit pattern else 0  static boolean findPattern(int n)  {  if (n <= 1) return false;  int x = n >> 1;  int y = x ^ n;  return (y & (y + 1)) == 0;  }  // Driver code  public static void main(String[] args)  {  int n = 10; // equal to 10101  if (findPattern(n))  System.out.println("Yes");  else  System.out.println("No");  } } // This code is contributed by karandeep1234 

# Returns True if n has alternate bit pattern else False def findPattern(n): if (n <= 1): return False x = n >> 1; y = x ^ n; return (y & (y+1)) == 0; # Driver code if __name__ == '__main__': n = 10 # equal to 10101 if findPattern(n): print("Yes") else: print("No") 

using System; public class Solution {  // Returns true if n has alternate bit pattern else  // false  static bool FindPattern(int n)  {  if (n <= 1) return false;   int x = n >> 1;  int y = x ^ n;  return (y & (y + 1)) == 0;  }  // Driver code  public static void Main(string[] args)  {  int n = 10; // equal to 10101  if (FindPattern(n))  Console.WriteLine("Yes");  else  Console.WriteLine("No");  } } 

// Returns true if n has alternate bit pattern else false function findPattern(n) {  if (n <= 1) return false; let x = n >> 1;  let y = x ^ n;  return (y & (y+1)) == 0; } let n = 21; // equal to 10101 if (findPattern(n)) {  console.log("Yes"); } else {  console.log("No"); } 

Yes 

Time Complexity: O(1)
Auxiliary Space: O(1)