Dado un entero positivo N , la tarea es encontrar el par de enteros (X, Y) tal que el XOR bit a bit de X e Y sea N y X * Y sea máximo donde el recuento de bits en X e Y sea menor que o igual a N.
Ejemplos:
Entrada: N = 10
Salida: 13 7
Explicación: El caso donde X = 13 e Y = 7 es la opción más óptima como 13 x o 7 = 10 y 13 * 7 = 91 que es el máximo posible.Entrada: N = 45
Salida: 50 31
Enfoque: El problema dado se puede resolver usando las siguientes observaciones:
- Si el i- ésimo bit de N es 0 , entonces el i- ésimo bit de X e Y debe ser 0 o 1 . Para maximizar el producto, establezca bits como 1 .
- Si el i- ésimo bit de N es 1 , entonces uno de los i- ésimos bits de X o Y debe ser 1 y el otro debe ser 0 . Dado que N debe tener un número constante de bits establecidos, la suma de X e Y debe ser constante.
- Si la suma de dos números es constante, su producto es máximo cuando se minimiza la diferencia entre los dos números.
De acuerdo con las observaciones anteriores, inicialice dos enteros X e Y como 0. Para minimizar la diferencia entre X e Y , X debe ser igual a MSB N e Y debe ser igual a N – MSB N donde MSB representa el más significativo poco _ Además, para todos los bits 0 en N , configure los bits respectivos en X e Y como 1 .
A continuación se muestra la implementación del enfoque anterior:
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 N
void 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 Code
int main()
{
int N = 45;
maximizeProduct(N);
return 0;
}
Java
// Java program for the above approach
import 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 N
static 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 Code
public static void main(String[] args)
{
int N = 45;
maximizeProduct(N);
}
}
// This code is contributed by dwivediyash
Python3
# python 3 program for the above approach import 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 N def 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 Code if __name__ == "__main__": N = 45 maximizeProduct(N) # This code is contributed by ukasp.
C#
// C# program for the above approach
using 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 N
static 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>
Producción:
50 31
Complejidad temporal: O(log N)
Espacio auxiliar: O(N)