Given a range [L, R], the task is to find a pair (X, Y), not necessarily distinct. Find the maximum possible value of the bitwise AND of the chosen integers.
Examples:
Input: L = 3, R = 7
Output: 7
Explanation:
In all the possible pairs, pair (7, 7) gives the maximum value for bitwise AND.
Input: L = 54, R = 55
Output: 55
Explanation:
In all the possible pairs, pair (55, 55) gives the maximum value for bitwise AND.
Naive Approach: To solve the problem mentioned above the naive method is to iterate from L to R and check the bitwise AND for every possible pair and print the maximum value in the end.
Time Complexity: O(N2)
Efficient Approach:
To optimize the above method we have to observe that here we have to integers L and R and we have to select two integers from the interval [L, R] so that their bitwise AND should be maximum. Bitwise AND of any two numbers between L and R will be always less than or equal to R only. So if we have to select two integers from the interval, we can choose the integers to be R and that’s the only way to maximize the bitwise AND.
Below is the implementation of above approach:
C
// C implementation to find the// Maximum Bitwise AND pair (X, Y)// from given range such that// X and Y can be same#include <stdio.h>// Function to return the// maximum bitwise ANDint maximumAND(int L, int R){ return R;}// Driver codeint main(){ int l = 3; int r = 7; printf("%d", maximumAND(l, r)); return 0;} |
C++
// C++ implementation to find the// Maximum Bitwise AND pair (X, Y)// from given range such that// X and Y can be same#include <bits/stdc++.h>using namespace std;// Function to return the// maximum bitwise ANDint maximumAND(int L, int R){ return R;}// Driver codeint main(){ int l = 3; int r = 7; cout << maximumAND(l, r); return 0;} |
Java
// Java implementation to find the// Maximum Bitwise AND pair (X, Y)// from given range such that// X and Y can be sameclass GFG { // Function to return the // maximum bitwise AND static int maximumAND(int L, int R) { return R; } // Driver code public static void main(String[] args) { int l = 3; int r = 7; System.out.print(maximumAND(l, r)); }} |
Python3
# Python3 implementation to find the # Maximum Bitwise AND pair (X, Y)# from given range such that# X and Y can be same# Function to return the# maximum bitwise AND def maximumAND(L, R): return R# Driver code if __name__ == '__main__': l = 3 r = 7 print(maximumAND(l, r)) |
C#
// C# implementation to find the// maximum Bitwise AND pair (X, Y)// from given range such that// X and Y can be sameusing System;class GFG{// Function to return the// maximum bitwise ANDstatic int maximumAND(int L, int R){ return R;}// Driver codepublic static void Main(String[] args){ int l = 3; int r = 7; Console.Write(maximumAND(l, r));}}// This code is contributed by amal kumar choubey |
Javascript
<script>// JavaScript implementation to find the// Maximum Bitwise AND pair (X, Y)// from given range such that// X and Y can be same// Function to return the // maximum bitwise AND function maximumAND(L, R) { return R; }// Driver Code let l = 3; let r = 7; document.write(maximumAND(l, r));</script> |
7
Time Complexity: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
