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++
// 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) |
Python3
# 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. |
PHP
<?php // PHP 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 $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 = floor ( $n / 2); } return true; } // Driver code $n = 10; if (findPattern( $n )) echo "Yes" ; else echo "No" ; return 0; // This code is contributed by nitin mittal. ?> |
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> |
Output:
Yes
Time Complexity: O(log2n)
Auxiliary Space: O(1)
An efficient approach to check if a number has bits in alternate patterns:
The idea is to check bitwise AND of n with (n>>1) and check if it returns 0. When bits are in an alternate fashion, the result will be 0 else not.
Below is the implementation of the above idea:
C++
// Program to demonstrate tree traversal with // ability to jump between nodes of same height #include <iostream> using namespace std; // Returns true if n has alternate bit pattern else false bool findPattern( int n) { if (n > 1) return ((n & (n >> 1))) == 0; else return false ; } // Driver code int main() { int n = 10; // equal to 10101 if (findPattern(n)) cout << "Yes" << endl; else cout << "No" << endl; return 0; } // This code is contributed by Prajwal Kandekar |
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 (!(n & (n >> 1))); else return 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
// Program to demonstrate tree traversal with // ability to jump between nodes of same height public class Solution { // Returns 1 if n has alternate bit pattern else 0 static boolean findPattern( int n) { if (n > 1 ) return ((n & (n >> 1 ))) == 0 ; else return false ; } // 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 |
Python3
# Program to demonstrate tree traversal with # ability to jump between nodes of same height # Returns True if n has alternate bit pattern else False def findPattern(n): if n > 1 : return ((n & (n >> 1 ))) = = 0 else : return False # Driver code if __name__ = = '__main__' : n = 10 # equal to 10101 if findPattern(n): print ( "Yes" ) else : print ( "No" ) |
Javascript
// Program to demonstrate tree traversal with // ability to jump between nodes of same height // Returns true if n has alternate bit pattern else false function findPattern(n) { if (n > 1) { return ((n & (n >> 1))) == 0; } else { return false ; } } let n = 21; // equal to 10101 if (findPattern(n)) { console.log( "Yes" ); } else { console.log( "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 ((n & (n >> 1))) == 0; else return false ; } // Driver code public static void Main( string [] args) { int n = 10; // equal to 10101 if (FindPattern(n)) Console.WriteLine( "Yes" ); else Console.WriteLine( "No" ); } } |
Yes
Time Complexity: O(1)
Auxiliary Space: O(1)
Reference:
http://stackoverflow.com/questions/38690278/program-to-check-whether-the-given-integer-has-an-alternate-pattern