Maximize the largest number K such that bitwise and of K till N is 0
Given an integer N, the task is to find the maximum value of K such that N & (N-1) & (N-2) & … & (K) = 0. Here & represents bitwise AND operator.
Example:
Input: N = 5
Output: 3
Explanation: The value of the expression 5 & 4 & 3 = 0. any value greater than 3 (example 4) will not satisfy
our given conditionInput: N =17
Output: 15
Naive approach: The brute force approach is to start from N-1 and perform bitwise AND operation till we get 0.
Below is the implementation of the above approach:
C++
// C++ program for above approach #include <bits/stdc++.h> using namespace std; // Function to find maximum value of k // which makes bitwise AND zero. int findMaxK( int N) { // Take k = N initially int K = N; // Start traversing from N-1 till 0 for ( int i = N - 1; i >= 0; i--) { K &= i; // Whenever we get AND as 0 // we stop and return if (K == 0) { return i; } } return 0; } // Driver Code int main() { int N = 5; cout << findMaxK(N); } |
Java
// Java program for the above approach import java.io.*; class GFG { // Function to find maximum value of k // which makes bitwise AND zero. static int findMaxK( int N) { // Take k = N initially int K = N; // Start traversing from N-1 till 0 for ( int i = N - 1 ; i >= 0 ; i--) { K &= i; // Whenever we get AND as 0 // we stop and return if (K == 0 ) { return i; } } return 0 ; } // Driver Code public static void main (String[] args) { int N = 5 ; System.out.println(findMaxK(N)); } } // This code is contributed by Potta Lokesh |
Python3
# Python 3 program for above approach # Function to find maximum value of k # which makes bitwise AND zero. def findMaxK(N): # Take k = N initially K = N # Start traversing from N-1 till 0 i = N - 1 while (i > = 0 ): K & = i # Whenever we get AND as 0 # we stop and return if (K = = 0 ): return i i - = 1 return 0 # Driver Code if __name__ = = '__main__' : N = 5 print (findMaxK(N)) # This code is contributed by ipg2016107. |
C#
// C# program for the above approach using System; class GFG { // Function to find maximum value of k // which makes bitwise AND zero. static int findMaxK( int N) { // Take k = N initially int K = N; // Start traversing from N-1 till 0 for ( int i = N - 1; i >= 0; i--) { K &= i; // Whenever we get AND as 0 // we stop and return if (K == 0) { return i; } } return 0; } // Driver Code public static void Main (String[] args) { int N = 5; Console.Write(findMaxK(N)); } } // This code is contributed by shivanisinghss2110 |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to find maximum value of k // which makes bitwise AND zero. function findMaxK(N) { // Take k = N initially let K = N; // Start traversing from N-1 till 0 for (let i = N - 1; i >= 0; i--) { K &= i; // Whenever we get AND as 0 // we stop and return if (K == 0) { return i; } } return 0; } // Driver Code let N = 5; document.write(findMaxK(N)); // This code is contributed by sanjoy_62. </script> |
3
Time complexity: O(N)
Auxiliary Space: O(1)
Efficient approach: By some observation, it can be seen that the answer is always equal to the highest power of 2, which is less than or equal to (N-1). So finally, the answer is always equal to 2^K -1, where K is some value.
Below is the implementation of the above approach:
C++
// C++ program for above approach #include <bits/stdc++.h> using namespace std; // Function to find maximum value of k // which makes bitwise AND zero. int findMaxK( int N) { // Finding the power less than N int p = log2(N); return pow (2, p); } // Driver Code int main() { int N = 5; cout << findMaxK(N) - 1 << endl; return 0; } |
Java
/*package whatever //do not write package name here */ import java.io.*; class GFG { // Function to find maximum value of k // which makes bitwise AND zero. static int findMaxK( int N) { // Finding the power less than N int p = ( int )(Math.log(N) / Math.log( 2 )); return ( int )Math.pow( 2 , p); } // Driver Code public static void main(String[] args) { int N = 5 ; System.out.println(findMaxK(N) - 1 ); } } // This code is contributed by maddler. |
Python3
import math # Function to find maximum value of k # which makes bitwise AND zero. def findMaxK(N): # Finding the power less than N p = math.log(N) / / math.log( 2 ); return int ( pow ( 2 , p)); # Driver Code N = 5 ; print (findMaxK(N) - 1 ); # This code is contributed by _saurabh_jaiswal |
C#
/*package whatever //do not write package name here */ using System; class GFG { // Function to find maximum value of k // which makes bitwise AND zero. static int findMaxK( int N) { // Finding the power less than N int p = ( int )(Math.Log(N) / Math.Log(2)); return ( int )Math.Pow(2, p); } // Driver Code public static void Main(String[] args) { int N = 5; Console.Write(findMaxK(N) - 1); } } // This code is contributed by shivanisinghss2110 |
Javascript
<script> /*package whatever //do not write package name here */ // Function to find maximum value of k // which makes bitwise AND zero. function findMaxK(N) { // Finding the power less than N var p = Math.log(N) / Math.log(2); return parseInt(Math.pow(2, p)); } // Driver Code var N = 5; document.write(findMaxK(N) - 1); // This code is contributed by 29AjayKumar </script> |
3
Time complexity: O(log N)
Auxiliary Space: O(1)