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 maximumint 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 Codeint main(){ // Given Number N int N = 10; // Function Call cout << maxORminusXOR(N); return 0;} |
Java
// Java program for the above approachimport 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 maximumstatic 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 Codepublic 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 approachimport 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 maximumdef 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 codeif __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 approachusing 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 maximumstatic 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 Codepublic 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 maximumfunction 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!
