Número mínimo de elementos que se eliminarán para hacer XOR máximo

Dado un número $norte$ donde $1\leq N\leq 10^{18}$ . La tarea es encontrar el número mínimo de elementos que se eliminarán en el medio $1$ para $norte$ que el XOR obtenido de los elementos restantes sea máximo.
Ejemplos :

Input: N = 5
Output: 2

Input: 1000000000000000
Output: 1

Planteamiento: Considerando los siguientes casos:

Caso 1: Cuando $n=1$ o $n=2$ , entonces la respuesta es 0 . No es necesario eliminar ningún elemento.
Caso 2: Ahora, tenemos que encontrar un número que sea potencia de 2 y mayor o igual que $norte$ .
Llamemos a este número ser $a$ .
Entonces, si $n = un$ o $n=a-1$ entonces simplemente eliminaremos $a-1$ . Por lo tanto la respuesta es 1 .
si no $n=a-2$ , entonces la respuesta es 0 . No es necesario eliminar ningún elemento.
Caso 3: De lo contrario, si $norte$ es $incluso$ , entonces la respuesta es 1 .
de lo contrario si $norte$ es $extraño$ , entonces la respuesta es 2 .

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ implementation to find minimum number of
// elements to remove to get maximum XOR value
#include <bits/stdc++.h>
using namespace std;
 
unsigned int nextPowerOf2(unsigned int n)
{
    unsigned count = 0;
 
    // First n in the below condition
    // is for the case where n is 0
    if (n && !(n & (n - 1)))
        return n;
 
    while (n != 0) {
        n >>= 1;
        count += 1;
    }
 
    return 1 << count;
}
 
// Function to find minimum number of
// elements to be removed.
int removeElement(unsigned int n)
{
 
    if (n == 1 || n == 2)
        return 0;
 
    unsigned int a = nextPowerOf2(n);
 
    if (n == a || n == a - 1)
        return 1;
 
    else if (n == a - 2)
        return 0;
 
    else if (n % 2 == 0)
        return 1;
 
    else
        return 2;
}
 
// Driver code
int main()
{
    unsigned int n = 5;
 
    // print minimum number of elements
    // to be removed
    cout << removeElement(n);
 
    return 0;
}

Java

//Java implementation to find minimum number of
//elements to remove to get maximum XOR value
public class GFG {
 
    static int nextPowerOf2(int n)
    {
     int count = 0;
 
     // First n in the below condition
     // is for the case where n is 0
     if (n!=0 && (n& (n - 1))==0)
         return n;
 
     while (n != 0) {
         n >>= 1;
         count += 1;
     }
 
     return 1 << count;
    }
 
    //Function to find minimum number of
    //elements to be removed.
    static int removeElement(int n)
    {
 
     if (n == 1 || n == 2)
         return 0;
 
     int a = nextPowerOf2(n);
 
     if (n == a || n == a - 1)
         return 1;
 
     else if (n == a - 2)
         return 0;
 
     else if (n % 2 == 0)
         return 1;
 
     else
         return 2;
    }
 
    //Driver code
    public static void main(String[] args) {
         
         int n = 5;
 
         // print minimum number of elements
         // to be removed
         System.out.println(removeElement(n));
    }
}

Python 3

# Python 3 to find minimum number
# of elements to remove to get
# maximum XOR value
 
def nextPowerOf2(n) :
    count = 0
 
    # First n in the below condition
    # is for the case where n is 0
    if (n and not(n and (n - 1))) :
        return n
 
    while n != 0 :
        n >>= 1
        count += 1
 
    return 1 << count
 
# Function to find minimum number
# of elements to be removed.
def removeElement(n) :
 
    if n == 1 or n == 2 :
        return 0
 
    a = nextPowerOf2(n)
     
    if n == a or n == a - 1 :
        return 1
 
    elif n == a - 2 :
        return 0
 
    elif n % 2 == 0 :
        return 1
 
    else :
        return 2
     
# Driver Code
if __name__ == "__main__" :
 
    n = 5
 
    # print minimum number of
    # elements to be removed
    print(removeElement(n))
 
# This code is contributed
# by ANKITRAI1

C#

//C# implementation to find minimum number of
//elements to remove to get maximum XOR value
 
using System;
public class GFG {
  
    static int nextPowerOf2(int n)
    {
     int count = 0;
  
     // First n in the below condition
     // is for the case where n is 0
     if (n!=0 && (n& (n - 1))==0)
         return n;
  
     while (n != 0) {
         n >>= 1;
         count += 1;
     }
  
     return 1 << count;
    }
  
    //Function to find minimum number of
    //elements to be removed.
    static int removeElement(int n)
    {
  
     if (n == 1 || n == 2)
         return 0;
  
     int a = nextPowerOf2(n);
  
     if (n == a || n == a - 1)
         return 1;
  
     else if (n == a - 2)
         return 0;
  
     else if (n % 2 == 0)
         return 1;
  
     else
         return 2;
    }
  
    //Driver code
    public static void Main() {
          
         int n = 5;
  
         // print minimum number of elements
         // to be removed
         Console.Write(removeElement(n));
    }
}

PHP

<?php
// PHP implementation to find
// minimum number of elements
// to remove to get maximum
// XOR value
 
function nextPowerOf2($n)
{
    $count = 0;
 
    // First n in the below condition
    // is for the case where n is 0
    if ($n && !($n & ($n - 1)))
        return $n;
 
    while ($n != 0)
    {
        $n >>= 1;
        $count += 1;
    }
 
    return 1 << $count;
}
 
// Function to find minimum number
// of elements to be removed.
function removeElement($n)
{
 
    if ($n == 1 || $n == 2)
        return 0;
 
    $a = nextPowerOf2($n);
 
    if ($n == $a || $n == $a - 1)
        return 1;
 
    else if ($n == $a - 2)
        return 0;
 
    else if ($n % 2 == 0)
        return 1;
 
    else
        return 2;
}
 
// Driver code
$n = 5;
 
// print minimum number of
// elements to be removed
echo removeElement($n);
 
// This code is contributed by mits
?>

Javascript

<script>
 
// Javascript implementation to
// find minimum number of
// elements to remove to get
// maximum XOR value
 
function nextPowerOf2(n)
{
    let count = 0;
 
    // First n in the below condition
    // is for the case where n is 0
    if (n && !(n & (n - 1)))
        return n;
 
    while (n != 0) {
        n >>= 1;
        count += 1;
    }
 
    return 1 << count;
}
 
// Function to find minimum number of
// elements to be removed.
function removeElement(n)
{
 
    if (n == 1 || n == 2)
        return 0;
 
    let a = nextPowerOf2(n);
 
    if (n == a || n == a - 1)
        return 1;
 
    else if (n == a - 2)
        return 0;
 
    else if (n % 2 == 0)
        return 1;
 
    else
        return 2;
}
 
// Driver code
    let n = 5;
 
    // print minimum number of elements
    // to be removed
    document.write(removeElement(n));
 
</script>

Producción:

Complejidad de tiempo: O (logn)

Publicación traducida automáticamente

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

C++

Java

Python 3

C#

PHP

Javascript

Deja una respuesta Cancelar la respuesta