Bitwise AND of all the odd numbers from 1 to N
Given an integer N, the task is to find the bitwise AND (&) of all the odd integers from the range [1, N].
Examples:
Input: N = 7
Output: 1
(1 & 3 & 5 & 7) = 1Input: N = 1
Output: 1
Naive approach: Starting from 1, bitwise AND all the odd numbers ? N.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <iostream> using namespace std; // Function to return the bitwise AND // of all the odd integers from // the range [1, n] int bitwiseAndOdd( int n) { // Initialize result to 1 int result = 1; // Starting from 3, bitwise AND // all the odd integers less // than or equal to n for ( int i = 3; i <= n; i = i + 2) { result = (result & i); } return result; } // Driver code int main() { int n = 10; cout << bitwiseAndOdd(n); return 0; } |
Java
// Java implementation of the approach class GFG { // Function to return the bitwise AND // of all the odd integers from // the range [1, n] static int bitwiseAndOdd( int n) { // Initialize result to 1 int result = 1 ; // Starting from 3, bitwise AND // all the odd integers less // than or equal to n for ( int i = 3 ; i <= n; i = i + 2 ) { result = (result & i); } return result; } // Driver code public static void main (String[] args) { int n = 10 ; System.out.println(bitwiseAndOdd(n)); } } // This code is contributed by AnkitRai01 |
Python3
# Python3 implementation of the approach # Function to return the bitwise AND # of all the odd integers from # the range [1, n] def bitwiseAndOdd(n) : # Initialize result to 1 result = 1 ; # Starting from 3, bitwise AND # all the odd integers less # than or equal to n for i in range ( 3 , n + 1 , 2 ) : result = (result & i); return result; # Driver code if __name__ = = "__main__" : n = 10 ; print (bitwiseAndOdd(n)); # This code is contributed by AnkitRai01 |
C#
// C# implementation of the approach using System; class GFG { // Function to return the bitwise AND // of all the odd integers from // the range [1, n] static int bitwiseAndOdd( int n) { // Initialize result to 1 int result = 1; // Starting from 3, bitwise AND // all the odd integers less // than or equal to n for ( int i = 3; i <= n; i = i + 2) { result = (result & i); } return result; } // Driver code public static void Main() { int n = 10; Console.WriteLine(bitwiseAndOdd(n)); } } // This code is contributed by AnkitRai01 |
Javascript
<script> // Javascript implementation of the approach // Function to return the bitwise AND // of all the odd integers from // the range [1, n] function bitwiseAndOdd(n) { // Initialize result to 1 var result = 1; // Starting from 3, bitwise AND // all the odd integers less // than or equal to n for ( var i = 3; i <= n; i = i + 2) { result = (result & i); } return result; } // Driver code var n = 10; document.write(bitwiseAndOdd(n)); // This code is contributed by noob2000 </script> |
Output:
1
Time Complexity: O(n)
Auxiliary Space: O(1)
Efficient approach: Bitwise AND with 1 will always give 1 as the result if the integer has a one at the least significant bit (all the odd integers in this case). So, the result will be 1 in all the cases.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <iostream> using namespace std; // Function to return the bitwise AND // of all the odd integers from // the range [1, n] int bitwiseAndOdd( int n) { return 1; } // Driver code int main() { int n = 10; cout << bitwiseAndOdd(n); return 0; } |
Java
// Java implementation of the approach class GFG { // Function to return the bitwise AND // of all the odd integers from // the range [1, n] static int bitwiseAndOdd( int n) { return 1 ; } // Driver code public static void main (String[] args) { int n = 10 ; System.out.println(bitwiseAndOdd(n)); } } // This code is contributed by AnkitRai01 |
Python 3
# Python 3 implementation of the approach # Function to return the bitwise AND # of all the odd integers from # the range [1, n] def bitwiseAndOdd(n): return 1 # Driver code n = 10 print (bitwiseAndOdd(n)) # This code is contributed by ApurvaRaj |
C#
// C# implementation of the approach using System; class GFG { // Function to return the bitwise AND // of all the odd integers from // the range [1, n] static int bitwiseAndOdd( int n) { return 1; } // Driver code public static void Main() { int n = 10; Console.WriteLine(bitwiseAndOdd(n)); } } // This code is contributed by AnkitRai01 |
Javascript
<script> // Javascript implementation of the approach // Function to return the bitwise AND // of all the odd integers from // the range [1, n] function bitwiseAndOdd(n) { return 1; } // Driver code var n = 10; document.write( bitwiseAndOdd(n)); //This code is contributed by SoumikMondal </script> |
Output:
1
Time Complexity: O(1)
Auxiliary Space: O(1)