Given a positive integer value V, the task is to find the maximum XOR of two numbers such that their product is equal to the given value V.
Examples:
Input: V = 20
Output: 7
Explanation: For the given value of 20, there are several pairs of numbers whose product is 20: (1, 20), (2, 10), and (4, 5). The maximum XOR among these pairs is 7, which corresponds to the pair (1, 20).Input: V = 36
Output: 39
Explanation: For the given value of 36, there are several pairs of numbers whose product is 36: (1, 36), (2, 18), (3, 12), (4, 9), and (6, 6). The maximum XOR among these pairs is 39, which corresponds to the pair (3, 12).
Approach: This can be solved with the following idea:
The approach takes advantage of the fact that if a and b are two numbers such that a * b = value, then the XOR of a and b will be maximum when a and b are as close to each other as possible. By iterating through the numbers up to the square root of the given value, we cover all possible pairs of factors and find the maximum XOR among them.
Below is the code for the above approach:
C++
// C++ code for the above approach:#include <cmath>#include <iostream>// Find maximum XOR pair valueint find_max_xor_product(int value){ int max_xor = 0; // Calculate the square // root of the given value int sqrt_value = sqrt(value); // Iterate from 1 to the square root // of the value for (int num = 1; num <= sqrt_value; ++num) { // Check if num is a divisor // of the value if (value % num == 0) { // Calculate the // corresponding divisor int div = value / num; max_xor = std::max(max_xor, num ^ div); } } // Return the maximum XOR value return max_xor;}// Driver codeint main(){ int value = 36; // Function call int max_xor = find_max_xor_product(value); std::cout << max_xor << std::endl; return 0;} |
Java
// Java code for the above approachimport java.util.*;public class GFG { // Find maximum XOR pair value public static int findMaxXorProduct(int value) { int max_xor = 0; // Calculate the square root of the given value int sqrt_value = (int)Math.sqrt(value); // Iterate from 1 to the square root of the value for (int num = 1; num <= sqrt_value; ++num) { // Check if num is a divisor of the value if (value % num == 0) { // Calculate the corresponding divisor int div = value / num; max_xor = Math.max(max_xor, num ^ div); } } // Return the maximum XOR value return max_xor; } public static void main(String[] args) { int value = 36; // Function call int max_xor = findMaxXorProduct(value); System.out.println(max_xor); }}// This code is contributed by Susobhan Akhuli |
Python3
#Python code for the above approach:import math# Find maximum XOR pair valuedef find_max_xor_product(value): max_xor = 0 # Calculate the square root of the given value sqrt_value = int(math.sqrt(value)) # Iterate from 1 to the square root of the value for num in range(1, sqrt_value + 1): # Check if num is a divisor of the value if value % num == 0: # Calculate the corresponding divisor div = value // num max_xor = max(max_xor, num ^ div) # Return the maximum XOR value return max_xor# Driver codeif __name__ == '__main__': value = 36 # Function call max_xor = find_max_xor_product(value) print(max_xor) |
C#
// C# code for the above approachusing System;public class GFG { // Find maximum XOR pair value static int FindMaxXorProduct(int value) { int max_xor = 0; // Calculate the square root // of the given value int sqrt_value = (int)Math.Sqrt(value); // Iterate from 1 to the square root // of the value for (int num = 1; num <= sqrt_value; ++num) { // Check if num is a divisor // of the value if (value % num == 0) { // Calculate the corresponding divisor int div = value / num; max_xor = Math.Max(max_xor, num ^ div); } } // Return the maximum XOR value return max_xor; } // Driver code static void Main(string[] args) { int value = 36; // Function call int max_xor = FindMaxXorProduct(value); Console.WriteLine(max_xor); }}// This code is contributed by Susobhan Akhuli |
Javascript
// JavaScript code for the above approach// Find maximum XOR pair valuefunction find_max_xor_product(value) { let max_xor = 0; // Calculate the square root of the given value let sqrt_value = Math.sqrt(value); // Iterate from 1 to the square root of the value for (let num = 1; num <= sqrt_value; ++num) { // Check if num is a divisor of the value if (value % num === 0) { // Calculate the corresponding divisor let div = value / num; max_xor = Math.max(max_xor, num ^ div); } } // Return the maximum XOR value return max_xor;}// Driver codelet value = 36;// Function calllet max_xor = find_max_xor_product(value);console.log(max_xor);// This code is contributed by Susobhan Akhuli |
37
Time complexity: O(sqrt(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!
