Given a natural number N, the task is to find the largest number M having the same length in binary representation as N such that the difference between N | M and N ^ M is maximum.
Examples:
Input: N = 6
Output: 7
Explanation:
All number numbers having same length in binary representation as N are 4, 5, 6, 7.
(6 | 4) – (6 ^ 4) = 4
(6 | 5) – (6 ^ 5) = 4
(6 | 6) – (6 ^ 6) = 6
(6 | 7) – (6 ^ 7) = 6
Hence, largest M for which (N | M) – (N ^ M) is maximum is 7Input: N = 10
Output: 15
Explanation:
The largest number M = 15 which has the same length in binary representation as 10 and the difference between N | M and N ^ M is maximum.
Naive Approach: The idea is to simply find all the numbers having the same length in binary representation as N and then for every number iterate and find the largest integer having (N | i) – (N ^ i) maximum.
Time Complexity: O(N)
Auxiliary Space: O(1)
Efficient Approach: The idea is to initialize M = 0 and iterate bit by bit in N (say i) and set or unset the ith bit of M according to the following 2 observations :
- When an ith bit of N is set: In this case, if we unset the ith bit of M, ith bit of both N | M and N^M will be set whereas on setting this bit of M, an ith bit of N|M will be set and N^M will be unset which will increase (N | M) – (N ^ M). Hence, it is optimal to set this bit of M.
- When an ith bit of N is unset: In this case, if we set this bit of M, both N|M and N^M will have this bit set or on keeping this bit of M unset both N|M and N^M will have this bit unset. So, in this case, we cannot increase the difference between them but as the requirement is to output the maximum M possible, so set this bit of M.
- From the above observations, it is clear that M will have all the bits set.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the largest number // M having the same length in binary // form as N such that the difference // between N | M and N ^ M is maximum int maxORminusXOR( int N) { // Find the most significant // bit of N int MSB = log2(N); // Initialize M int M = 0; // Set all the bits of M for ( int i = 0; i <= MSB; i++) M += (1 << i); // Return the answer return M; } // Driver Code int main() { // Given Number N int N = 10; // Function Call cout << maxORminusXOR(N); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to find the largest number // M having the same length in binary // form as N such that the difference // between N | M and N ^ M is maximum static int maxORminusXOR( int N) { // Find the most significant // bit of N int MSB = ( int )Math.ceil(Math.log(N)); // Initialize M int M = 0 ; // Set all the bits of M for ( int i = 0 ; i <= MSB; i++) M += ( 1 << i); // Return the answer return M; } // Driver Code public static void main(String[] args) { // Given number N int N = 10 ; // Function call System.out.print(maxORminusXOR(N)); } } // This code is contributed by Rajput-Ji |
Python3
# Python3 program for the above approach import math # Function to find the largest number # M having the same length in binary # form as N such that the difference # between N | M and N ^ M is maximum def maxORminusXOR(N): # Find the most significant # bit of N MSB = int (math.log2(N)); # Initialize M M = 0 # Set all the bits of M for i in range (MSB + 1 ): M + = ( 1 << i) # Return the answer return M # Driver code if __name__ = = '__main__' : # Given Number N N = 10 # Function call print (maxORminusXOR(N)) # This code is contributed by jana_sayantan |
C#
// C# program for the above approach using System; class GFG{ // Function to find the largest number // M having the same length in binary // form as N such that the difference // between N | M and N ^ M is maximum static int maxORminusXOR( int N) { // Find the most significant // bit of N int MSB = ( int )Math.Ceiling(Math.Log(N)); // Initialize M int M = 0; // Set all the bits of M for ( int i = 0; i <= MSB; i++) M += (1 << i); // Return the answer return M; } // Driver Code public static void Main(String[] args) { // Given number N int N = 10; // Function call Console.Write(maxORminusXOR(N)); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript implementation of the above approach // Function to find the largest number // M having the same length in binary // form as N such that the difference // between N | M and N ^ M is maximum function maxORminusXOR(N) { // Find the most significant // bit of N let MSB = Math.ceil(Math.log(N)); // Initialize M let M = 0; // Set all the bits of M for (let i = 0; i <= MSB; i++) M += (1 << i); // Return the answer return M; } // Driver code // Given number N let N = 10; // Function call document.write(maxORminusXOR(N)); // This code is contributed by code_hunt. </script> |
15
Time Complexity: O(log N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!