Given a positive integer N, the task is to find the pair of integers (X, Y) such that the Bitwise XOR of X and Y is N and X * Y is maximum where the count of bits in X and Y is less than or equal to N.
Examples:
Input: N = 10
Output: 13 7
Explanation: The case where X = 13 and Y = 7 is the most optimal choice as 13 xor 7 = 10 and 13 * 7 = 91 which is maximum possible.Input: N = 45
Output: 50 31
Approach: The given problem can be solved using the following observations:
- If the ith bit of N is 0, then the ith bit of both X and Y must be either 0 or 1. In order to maximize the product, set such bits as 1.
- If the ith bit of N is 1, then one of the ith bits of X or Y must be 1 and the other must be 0. Since N must have a constant number of set bits, therefore the sum of X and Y must be constant.
- If the sum of two numbers is constant, their product is maximum when the difference between the two numbers is minimized.
According to the above observations, initialize two integers X and Y as 0. In order to minimize the difference between X and Y, X must be equal to the MSBN and Y must be equal to N – MSBN where MSB represents the Most Significant Bit. Also, for all the 0 bits in N, set the respective bits in both X and Y as 1.
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 pair (X, Y) such// that X xor Y = N and the count of set// bits in X and Y is less than count of// set bit in Nvoid maximizeProduct(int N){ // Stores MSB (Most Significant Bit) int MSB = (int)log2(N); // Stores the value of X int X = 1 << MSB; // Stores the value of Y int Y = N - (1 << MSB); // Traversing over all bits of N for (int i = 0; i < MSB; i++) { // If ith bit of N is 0 if (!(N & (1 << i))) { // Set ith bit of X to 1 X += 1 << i; // Set ith bit of Y to 1 Y += 1 << i; } } // Print Answer cout << X << " " << Y;}// Driver Codeint main(){ int N = 45; maximizeProduct(N); return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG{// Function to find the pair (X, Y) such// that X xor Y = N and the count of set// bits in X and Y is less than count of// set bit in Nstatic void maximizeProduct(int N){ // Stores MSB (Most Significant Bit) int MSB = (int)(Math.log(N) / Math.log(2)); // Stores the value of X int X = 1 << MSB; // Stores the value of Y int Y = N - (1 << MSB); // Traversing over all bits of N for (int i = 0; i < MSB; i++) { // If ith bit of N is 0 if ((N & (1 << i))==0) { // Set ith bit of X to 1 X += 1 << i; // Set ith bit of Y to 1 Y += 1 << i; } } // Print Answer System.out.println(X+" "+Y);}// Driver Codepublic static void main(String[] args){ int N = 45; maximizeProduct(N);}}// This code is contributed by dwivediyash |
Python3
# python 3 program for the above approachimport math# Function to find the pair (X, Y) such# that X xor Y = N and the count of set# bits in X and Y is less than count of# set bit in Ndef maximizeProduct(N): # Stores MSB (Most Significant Bit) MSB = (int)(math.log2(N)) # Stores the value of X X = 1 << MSB # / Stores the value of Y Y = N - (1 << MSB) # Traversing over all bits of N for i in range(MSB): # If ith bit of N is 0 if (not (N & (1 << i))): # / Set ith bit of X to 1 X += 1 << i # Set ith bit of Y to 1 Y += 1 << i # Print Answer print(X, Y)# Driver Codeif __name__ == "__main__": N = 45 maximizeProduct(N) # This code is contributed by ukasp. |
C#
// C# program for the above approachusing System;class GFG {// Function to find the pair (X, Y) such// that X xor Y = N and the count of set// bits in X and Y is less than count of// set bit in Nstatic void maximizeProduct(int N){ // Stores MSB (Most Significant Bit) int MSB = (int)(Math.Log(N) / Math.Log(2)); // Stores the value of X int X = 1 << MSB; // Stores the value of Y int Y = N - (1 << MSB); // Traversing over all bits of N for (int i = 0; i < MSB; i++) { // If ith bit of N is 0 if ((N & (1 << i))==0) { // Set ith bit of X to 1 X += 1 << i; // Set ith bit of Y to 1 Y += 1 << i; } } // Print Answer Console.Write(X+" "+Y);} // Driver Code public static void Main() { int N = 45; maximizeProduct(N); }}// This code is contributed by code_hunt. |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to find the pair (X, Y) such // that X xor Y = N and the count of set // bits in X and Y is less than count of // set bit in N function maximizeProduct(N) { // Stores MSB (Most Significant Bit) let MSB = Math.log2(N); // Stores the value of X let X = 1 << MSB; // Stores the value of Y let Y = N - (1 << MSB); // Traversing over all bits of N for (let i = 0; i < MSB; i++) { // If ith bit of N is 0 if (!(N & (1 << i))) { // Set ith bit of X to 1 X += 1 << i; // Set ith bit of Y to 1 Y += 1 << i; } } // Print Answer document.write(X + " " + Y); } // Driver Code let N = 45; maximizeProduct(N);// This code is contributed by Potta Lokesh </script> |
Output:
50 31
Time Complexity: O(log N)
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!
