Dados dos enteros positivos X y K , la tarea es encontrar el K -ésimo entero positivo más pequeño ( Y ) tal que la suma de X e Y sea igual a Bitwise OR de X e Y , es decir (X + Y = X | Y)
Ejemplos:
Entrada: X = 5, K = 1
Salida: 2
Explicación:
Considere el número más pequeño como 2. La suma de 2 y 5 es 2 + 5 = 7 y el OR bit a bit de 2 y 5 es 7.Entrada: X = 5, K = 5
Salida: 18
Enfoque: El problema dado se puede resolver mediante la siguiente observación:
- Usando las propiedades del operador bit a bit en dos números X e Y :
(X + Y) = (X e Y) + (X | Y)
- Por lo tanto, para que el valor de X + Y sea el mismo que X | Y , el valor de X e Y debe ser 0 .
- Además, sabemos que para que X e Y sean 0, la posición de los bits activados en X debe estar desactivada en Y, y las posiciones de los bits desactivados de X pueden ser 0 o 1 en Y.
- Por lo tanto, para encontrar el K-ésimo número positivo más pequeño que cumpla las condiciones anteriores, podemos usar combinaciones para las posiciones de bits de Y que no están configuradas en X.
Para implementar lo anterior, itere la representación binaria de X de derecha a izquierda y, en cada iteración, considere los siguientes casos:
- Si el bit actual de X es 1, el bit correspondiente en Y será 0, para obtener (X & Y) como 0.
- Si el bit actual de X es 0 y el bit más a la derecha de K es 1, el bit correspondiente de Y será 1. Esto significa que se han usado dos combinaciones en el bit actual en Y: primero 0 y luego 1. Luego divida K por 2
- Si el bit actual de X es 0 y el bit más a la derecha de K es 0, el bit correspondiente de Y será 0. Esto significa que solo se ha utilizado una combinación en el bit actual en Y: 0. Luego divida K por 2
- Si K se convierte en 0, rompa el bucle e indique que se ha encontrado el número K.
Finalmente, imprima la conversión decimal de Y como la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate K-th smallest
// solution(Y) of equation X+Y = X|Y
long long KthSolution(long long X,
long long K)
{
// Initialize the variable
// to store the answer
long long ans = 0;
for (int i = 0; i < 64; i++) {
// The i-th bit of X is off
if (!(X & (1LL << i))) {
// The i-bit of K is on
if (K & 1) {
ans |= (1LL << i);
}
// Divide K by 2
K >>= 1;
// If K becomes 0 then break
if (!K) {
break;
}
}
}
return ans;
}
// Driver Code
int main()
{
long long X = 10, K = 5;
cout << KthSolution(X, K);
return 0;
}
Java
/*package whatever //do not write package name here */
import java.io.*;
class GFG
{
// Function to calculate K-th smallest
// solution(Y) of equation X+Y = X|Y
static long KthSolution(long X, long K)
{
// Initialize the variable
// to store the answer
long ans = 0;
for (int i = 0; i < 64; i++) {
// The i-th bit of X is off
if ((X & (1 << i)) == 0) {
// The i-bit of K is on
if ((K & 1) > 0) {
ans |= (1 << i);
}
// Divide K by 2
K >>= 1;
// If K becomes 0 then break
if (K == 0) {
break;
}
}
}
return ans;
}
// Driver Code
public static void main(String[] args)
{
long X = 10;
long K = 5;
System.out.println(KthSolution(X, K));
}
}
// This code is contributed by maddler.
Python3
# Python Program to implement # the above approach # Function to calculate K-th smallest # solution(Y) of equation X+Y = X|Y def KthSolution(X, K): # Initialize the variable # to store the answer ans = 0 for i in range(64): # The i-th bit of X is off if not (X & (1 << i)): # The i-bit of K is on if (K & 1): ans |= (1 << i) # Divide K by 2 K >>= 1 # If K becomes 0 then break if not K: break return ans # Driver Code X = 10 K = 5 print(KthSolution(X, K)) # This code is contributed by Saurabh Jaiswal
C#
/*package whatever //do not write package name here */
using System;
public class GFG
{
// Function to calculate K-th smallest
// solution(Y) of equation X+Y = X|Y
static long KthSolution(long X, long K)
{
// Initialize the variable
// to store the answer
int ans = 0;
for (int i = 0; i < 64; i++) {
// The i-th bit of X is off
if ((X & (1 << i)) == 0) {
// The i-bit of K is on
if ((K & 1) > 0) {
ans |= (1 << i);
}
// Divide K by 2
K >>= 1;
// If K becomes 0 then break
if (K == 0) {
break;
}
}
}
return ans;
}
// Driver Code
public static void Main(String[] args)
{
long X = 10;
long K = 5;
Console.WriteLine(KthSolution(X, K));
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to calculate K-th smallest
// solution(Y) of equation X+Y = X|Y
function KthSolution(X,K)
{
// Initialize the variable
// to store the answer
let ans = 0;
for (let i = 0; i < 64; i++) {
// The i-th bit of X is off
if (!(X & (1 << i))) {
// The i-bit of K is on
if (K & 1) {
ans |= (1 << i);
}
// Divide K by 2
K >>= 1;
// If K becomes 0 then break
if (!K) {
break;
}
}
}
return ans;
}
// Driver Code
let X = 10, K = 5;
document.write(KthSolution(X, K));
// This code is contributed by Potta Lokesh
</script>
Producción:
17
Complejidad de tiempo: O(log(X))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por kartikmodi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA