Check if a number has bits in alternate pattern | Set 1
Last Updated : 18 Mar, 2025
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++ // 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 // 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 // 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)
Python # 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.
C# // 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.
JavaScript <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>
Time Complexity: O(log2n)
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.
C++ #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 // 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"
Java 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
Python # 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")
C# 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"); } }
JavaScript // 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"); }
Time Complexity: O(1)
Auxiliary Space: O(1)