XOR mínimo de como máximo K elementos en el rango [L, R]

Posted on by Rudeus Greyrat

Dados tres enteros L , R y K , la tarea es encontrar el XOR bit a bit mínimo de como máximo K enteros entre [L, R] .

Ejemplos:

Entrada: L = 1, R = 10, K = 3
Salida: 0
Explicación:
Elija los elementos 4, 5 y 1 en el rango [1, 10] y el Bitwise XOR de los elementos elegidos es 0, que es el mínimo. 

Entrada: L = 32, R = 33, K = 2
Salida: 1
Explicación:
Elija los elementos 32 y 33 en el rango [32, 33] y el Bitwise XOR de los elementos elegidos es 1, que es el mínimo.

Enfoque: Una observación que nos ayuda a resolver el problema es el XOR bit a bit  de dos números X y (X+1) es 1 si X es un número par. Así, el Bitwise XOR de cuatro números consecutivos sería 0 si el primero es par.

Siga los pasos a continuación para resolver el problema:

  • Si el valor de K es mayor que 4 , la respuesta siempre es 0. (Esto se debe a que siempre se pueden encontrar cuatro números X, (X+1), (X+2) y (X+3) en un rango de 5 donde X es un número par).
  • Si el valor de K es 2 , llame a la función func2() que toma L, R y K como parámetros de entrada y hace lo siguiente:
    • Si el valor de (RL) es mayor o igual a 2 , es decir, hay al menos 3 números en el rango, devuelve 1. (Esto se debe a que dos números X y X+1 siempre se pueden encontrar en un rango de 3 donde X es un número par).
    • De lo contrario, devuelve el mínimo de L y (L^R).
  • Si el valor de K es 3 , llame a la función func3() que toma L, R y K como parámetros de entrada y hace lo siguiente:
    • Si (R^L) se encuentra entre L y R , devuelve 0 . (Esto se debe a que (R^L)^L^R=0) )
    • De lo contrario, devuelve func2 (L, R, K)
  • Si el valor de K es 4 , llame a la función func4() que toma L, R y K como parámetros de entrada y hace lo siguiente:
    • Si (RL) es mayor o igual a 4 , es decir, hay al menos 5 números en el rango, devuelve 0. (Esto se debe a que cuatro números X,(X+1),(X+2) y (X+ 3) siempre se puede encontrar en un rango de 5 donde X es un número par).
    • De lo contrario, devuelva el mínimo de Xor de los cuatro números en el rango [L, R] y func3(L, R, K) .
  • De lo contrario, devuelve L.

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 for K=2
int func2(int L, int R, int K)
{
    if (R - L >= 2)
        return 1;
    return min(L, L ^ R);
}
// Function for K=2
int func3(int L, int R, int K)
{
    if ((R ^ L) > L && (R ^ L) < R)
        return 0;
    return func2(L, R, K);
}
// Function for K=2
int func4(int L, int R, int K)
{
    if (R - L >= 4)
        return 0;
    int minval = L ^ (L + 1) ^ (L + 2) ^ (L + 3);
    return min(minval, func3(L, R, K));
}
// Function to calculate the minimum XOR of at most K
// elements in [L, R]
int minimumXor(int L, int R, int K)
{
    if (K > 4)
        return 0;
    else if (K == 4)
        return func4(L, R, K);
    else if (K == 3)
        return func3(L, R, K);
    else if (K == 2)
        return func2(L, R, K);
    else
        return L;
}
// Driver code
int main()
{
    // Input
    int L = 1, R = 3, K = 3;
    // Function call
    cout << minimumXor(L, R, K) << endl;
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
 
class GFG
{
 
// Function for K=2
static int func2(int L, int R, int K)
{
    if (R - L >= 2)
        return 1;
    return Math.min(L, L ^ R);
}
    
// Function for K=2
static int func3(int L, int R, int K)
{
    if ((R ^ L) > L && (R ^ L) < R)
        return 0;
    return func2(L, R, K);
}
    
// Function for K=2
static int func4(int L, int R, int K)
{
    if (R - L >= 4)
        return 0;
    int minval = L ^ (L + 1) ^ (L + 2) ^ (L + 3);
    return Math.min(minval, func3(L, R, K));
}
// Function to calculate the minimum XOR of at most K
// elements in [L, R]
static int minimumXor(int L, int R, int K)
{
    if (K > 4)
        return 0;
    else if (K == 4)
        return func4(L, R, K);
    else if (K == 3)
        return func3(L, R, K);
    else if (K == 2)
        return func2(L, R, K);
    else
        return L;
}
 
  // Driver code
  public static void main(String[] args)
  {
      // Input
    int L = 1, R = 3, K = 3;
    
    // Function call
    System.out.println( minimumXor(L, R, K));
  }
}
 
// This code is contributed by sanjoy_62.

Python3

# Python program for the above approach
 
# Function for K=2
def func2(L, R, K):
    if (R - L >= 2):
        return 1
    return min(L, L ^ R)
 
  # Function for K=2
def func3(L, R, K):
    if ((R ^ L) > L and (R ^ L) < R):
        return 0
    return func2(L, R, K)
   
# Function for K=2
def func4(L, R, K):
    if (R - L >= 4):
        return 0
    minval = L ^ (L + 1) ^ (L + 2) ^ (L + 3)
    return min(minval, func3(L, R, K))
   
# Function to calculate the minimum XOR of at most K
# elements in [L, R]
def minimumXor(L, R, K):
    if (K > 4):
        return 0
    elif (K == 4):
        return func4(L, R, K)
    elif (K == 3):
        return func3(L, R, K)
    elif (K == 2):
        return func2(L, R, K)
    else:
        return L
 
# Driver code
if __name__ == '__main__':
   
    # Input
    L, R, K = 1, 3, 3
     
    # Function call
    print (minimumXor(L, R, K))
 
# This code is contributed by mohit kumar 29.

C#

// C# program for the above approach
using System;
class GFG
{
 
// Function for K=2
static int func2(int L, int R, int K)
{
    if (R - L >= 2)
        return 1;
    return Math.Min(L, L ^ R);
}
   
// Function for K=2
static int func3(int L, int R, int K)
{
    if ((R ^ L) > L && (R ^ L) < R)
        return 0;
    return func2(L, R, K);
}
   
// Function for K=2
static int func4(int L, int R, int K)
{
    if (R - L >= 4)
        return 0;
    int minval = L ^ (L + 1) ^ (L + 2) ^ (L + 3);
    return Math.Min(minval, func3(L, R, K));
}
// Function to calculate the minimum XOR of at most K
// elements in [L, R]
static int minimumXor(int L, int R, int K)
{
    if (K > 4)
        return 0;
    else if (K == 4)
        return func4(L, R, K);
    else if (K == 3)
        return func3(L, R, K);
    else if (K == 2)
        return func2(L, R, K);
    else
        return L;
}
 
 
// Driver code
static void Main()
{
    // Input
    int L = 1, R = 3, K = 3;
   
    // Function call
    Console.Write( minimumXor(L, R, K));
 
}
}
 
// This code is contributed by code_hunt.

Javascript

<script>
 
// Javascript program for the above approach
 
// Function for K=2
function func2(L, R, K)
{
    if (R - L >= 2)
        return 1;
         
    return Mat.min(L, L ^ R);
}
 
// Function for K=2
function func3(L, R, K)
{
    if ((R ^ L) > L && (R ^ L) < R)
        return 0;
         
    return func2(L, R, K);
}
 
// Function for K=2
function func4(L, R, K)
{
    if (R - L >= 4)
        return 0;
         
    var minval = L ^ (L + 1) ^
                (L + 2) ^ (L + 3);
    return Math.min(minval, func3(L, R, K));
}
 
// Function to calculate the minimum XOR
// of at most K elements in [L, R]
function minimumXor(L, R, K)
{
    if (K > 4)
        return 0;
    else if (K == 4)
        return func4(L, R, K);
    else if (K == 3)
        return func3(L, R, K);
    else if (K == 2)
        return func2(L, R, K);
    else
        return L;
}
 
// Driver code
 
// Input
var L = 1, R = 3, K = 3;
 
// Function call
document.write(minimumXor(L, R, K));
 
// This code is contributed by SURENDRA_GANGWAR
 
</script>
Producción

0

Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por chsadik99 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *