Given a natural number N, the task is to find a number M smaller than N such that the difference between their bitwise XOR (N ^ M) and bitwise AND (N & M) is maximum.
Examples:
Input: N = 4
Output: 3
Explanation:
(4 ^ 0) – (4 & 0) = 4
(4 ^ 1) – (4 & 1) = 5
(4 ^ 2) – (4 & 2) = 6
(4 ^ 3) – (4 & 3) = 7
Hence, the value of M is 3.Input: N = 6
Output: 1
Explanation:
The difference between N ^ M and N & M is maximum when M = 1.
Naive Approach: The idea is to iterate for every element less than N and find M for which N^M – N&M is maximum. Below are the steps:
- Initialize a variable let’s say maxDiff with 0 and M with -1.
- Iterate from 0 to N-1 and calculate diff = N^i -N&i.
- If diff is greater or equal to maxDiff assign M = i and maxDiff = diff.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to return M<N such that// N^M - N&M is maximumint getMaxDifference(int N){ // Initialize variables int M = -1; int maxDiff = 0; // Iterate for all values < N for (int i = 0; i < N; i++) { // Find the difference between // Bitwise XOR and AND int diff = (N ^ i) - (N & i); // Check if new difference is // greater than previous maximum if (diff >= maxDiff) { // Update variables maxDiff = diff; M = i; } } // Return the answer return M;}// Driver Codeint main(){ // Given Number N int N = 6; // Function Call cout << getMaxDifference(N); return 0;} |
Java
// Java program for the above approachclass GFG{// Function to return M<N such that// N^M - N&M is maximumstatic int getMaxDifference(int N){ // Initialize variables int M = -1; int maxDiff = 0; // Iterate for all values < N for (int i = 0; i < N; i++) { // Find the difference between // Bitwise XOR and AND int diff = (N ^ i) - (N & i); // Check if new difference is // greater than previous maximum if (diff >= maxDiff) { // Update variables maxDiff = diff; M = i; } } // Return the answer return M;}// Driver Codepublic static void main(String[] args){ // Given Number N int N = 6; // Function Call System.out.print(getMaxDifference(N));}}// This code is contributed by Rohit_ranjan |
Python3
# Python3 program for the above approach# Function to return M<N such that# N^M - N&M is maximumdef getMaxDifference(N): # Initialize variables M = -1; maxDiff = 0; # Iterate for all values < N for i in range(N): # Find the difference between # Bitwise XOR and AND diff = (N ^ i) - (N & i); # Check if new difference is # greater than previous maximum if (diff >= maxDiff): # Update variables maxDiff = diff; M = i; # Return the answer return M;# Driver Codeif __name__ == '__main__': # Given number N N = 6; # Function call print(getMaxDifference(N));# This code is contributed by amal kumar choubey |
C#
// C# program for the above approachusing System;class GFG{// Function to return M<N such that// N^M - N&M is maximumstatic int getMaxDifference(int N){ // Initialize variables int M = -1; int maxDiff = 0; // Iterate for all values < N for(int i = 0; i < N; i++) { // Find the difference between // Bitwise XOR and AND int diff = (N ^ i) - (N & i); // Check if new difference is // greater than previous maximum if (diff >= maxDiff) { // Update variables maxDiff = diff; M = i; } } // Return the answer return M;}// Driver Codepublic static void Main(String[] args){ // Given number N int N = 6; // Function call Console.Write(getMaxDifference(N));}}// This code is contributed by Rajput-Ji |
Javascript
<script>// javascript program for the above approach // Function to return M<N such that // N^M - N&M is maximum function getMaxDifference(N) { // Initialize variables var M = -1; var maxDiff = 0; // Iterate for all values < N for (i = 0; i < N; i++) { // Find the difference between // Bitwise XOR and AND var diff = (N ^ i) - (N & i); // Check if new difference is // greater than previous maximum if (diff >= maxDiff) { // Update variables maxDiff = diff; M = i; } } // Return the answer return M; } // Driver Code // Given Number N var N = 6; // Function Call document.write(getMaxDifference(N));// This code contributed by aashish1995</script> |
Output:
1
Time Complexity: O(N)
Auxiliary Space: O(1)
Efficient Approach: The idea is to observe that the difference between Bitwise XOR and Bitwise AND is maximum if Bitwise AND of the two numbers is the minimum possible number and the minimum possible number is 0.
The Bitwise AND between the two numbers is zero if and only if they complement each other. Therefore, the possible value of M must be the complement of the given number N.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to flip all bits of Nint findM(int N){ int M = 0; // Finding most significant bit of N int MSB = (int)log2(N); // Calculating required number for (int i = 0; i < MSB; i++) { if (!(N & (1 << i))) M += (1 << i); } // Return the answer return M;}// Driver Codeint main(){ // Given Number int N = 6; // Function Call cout << findM(N); return 0;} |
Java
// Java program for the above approachclass GFG{// Function to flip all bits of Nstatic int findM(int N){ int M = 0; // Finding most significant bit of N int MSB = (int)Math.log(N); // Calculating required number for(int i = 0; i < MSB; i++) { if ((N & (1 << i)) == 0) M += (1 << i); } // Return the answer return M;}// Driver Codepublic static void main(String[] args){ // Given number int N = 6; // Function call System.out.print(findM(N));}}// This code is contributed by Rajput-Ji |
Python3
# Python3 program for the above approachimport math# Function to flip all bits of Ndef findM(N): M = 0; # Finding most significant bit of N MSB = int(math.log(N)); # Calculating required number for i in range(MSB): if ((N & (1 << i)) == 0): M += (1 << i); # Return the answer return M;# Driver Codeif __name__ == '__main__': # Given number N = 6; # Function call print(findM(N));# This code is contributed by Amit Katiyar |
C#
// C# program for the above approachusing System;class GFG{// Function to flip all bits of Nstatic int findM(int N){ int M = 0; // Finding most significant bit of N int MSB = (int)Math.Log(N); // Calculating required number for(int i = 0; i < MSB; i++) { if ((N & (1 << i)) == 0) M += (1 << i); } // Return the answer return M;}// Driver Codepublic static void Main(String[] args){ // Given number int N = 6; // Function call Console.Write(findM(N));}}// This code is contributed by Amit Katiyar |
Javascript
<script>// javascript program for the above approach // Function to flip all bits of N function findM(N) { var M = 0; // Finding most significant bit of N var MSB = parseInt( Math.log(N)); // Calculating required number for (i = 0; i < MSB; i++) { if ((N & (1 << i)) == 0) M += (1 << i); } // Return the answer return M; } // Driver Code // Given number var N = 6; // Function call document.write(findM(N));// This code is contributed by Rajput-Ji </script> |
Output:
1
Time Complexity: O(log2N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
