Efficiently check whether n is a multiple of 4 or not
Given a number n. The problem is to efficiently check whether n is a multiple of 4 or not without using arithmetic operators.
Examples:
Input : 16 Output : Yes Input : 14 Output : No
Approach: A multiple of 4 always has 00 as its last two digits in its binary representation. We have to check whether the last two digits of n are unset or not.
How to check whether the last two bits are unset or not.
If n & 3 == 0, then the last two bits are unset, else either both or one of them are set.
C++
// C++ implementation to efficiently check whether n // is a multiple of 4 or not #include <bits/stdc++.h> using namespace std; // function to check whether 'n' is // a multiple of 4 or not string isAMultipleOf4( int n) { // if true, then 'n' is a multiple of 4 if ((n & 3) == 0) return "Yes" ; // else 'n' is not a multiple of 4 return "No" ; } // Driver program to test above int main() { int n = 16; cout << isAMultipleOf4(n); return 0; } |
Java
// Java implementation to efficiently check // whether n is a multiple of 4 or not class GFG { // method to check whether 'n' is // a multiple of 4 or not static boolean isAMultipleOf4( int n) { // if true, then 'n' is a multiple of 4 if ((n & 3 ) == 0 ) return true ; // else 'n' is not a multiple of 4 return false ; } // Driver method public static void main(String[] args) { int n = 16 ; System.out.println(isAMultipleOf4(n) ? "Yes" : "No" ); } } |
Python 3
# Python 3 implementation to # efficiently check whether n # is a multiple of 4 or not # function to check whether 'n' # is a multiple of 4 or not def isAMultipleOf4(n): # if true, then 'n' is # a multiple of 4 if ((n & 3 ) = = 0 ): return "Yes" # else 'n' is not a # multiple of 4 return "No" # Driver Code if __name__ = = "__main__" : n = 16 print (isAMultipleOf4(n)) # This code is contributed # by ChitraNayal |
C#
// C# implementation to efficiently check // whether n is a multiple of 4 or not using System; class GFG { // method to check whether 'n' is // a multiple of 4 or not static bool isAMultipleOf4( int n) { // if true, then 'n' is a multiple of 4 if ((n & 3) == 0) return true ; // else 'n' is not a multiple of 4 return false ; } // Driver method public static void Main() { int n = 16; Console.WriteLine(isAMultipleOf4(n) ? "Yes" : "No" ); } } // This code is contributed by vt_m. |
PHP
<?php // PHP implementation to // efficiently check whether n // is a multiple of 4 or not // function to check whether 'n' is // a multiple of 4 or not function isAMultipleOf4( $n ) { // if true, then 'n' // is a multiple of 4 if (( $n & 3) == 0) return "Yes" ; // else 'n' is not // a multiple of 4 return "No" ; } // Driver Code $n = 16; echo isAMultipleOf4( $n ); // This code is contributed by anuj_67. ?> |
Javascript
<script> // Javascript implementation to efficiently check // whether n is a multiple of 4 or not // method to check whether 'n' is // a multiple of 4 or not function isAMultipleOf4(n) { // if true, then 'n' is a multiple of 4 if ((n & 3) == 0) return true ; // else 'n' is not a multiple of 4 return false ; } // Driver method let n = 16; document.write(isAMultipleOf4(n) ? "Yes" : "No" ); //This code is contributed by rag2127 </script> |
Output:
Yes
Time Complexity : O(1)
Auxiliary Space: O(1)
Can we generalize above solution?
Similarly we can check for other powers of 2. For example, a number n would be multiple of 8 if n & 7 is 0. In general we can say.
// x must be a power of 2 for below // logic to work if (n & (x -1) == 0) n is a multiple of x Else n is NOT a multiple of x
Contact Us