El mayor número M menor que N tal que XOR de M y N es par

Dado un entero positivo N , la tarea es encontrar el entero más grande M tal que 0 <= M < N y XOR(M, N) sea un número par. Si tal valor de M no se puede obtener para N dado , imprima -1 .

Ejemplos:

Entrada: N = 10 
Salida: 8 
Explicación: 
(10 XOR 9) = 3, por lo que M = 9 no es posible porque 3 no es un número par. 
(10 XOR 8) = 2, por lo que M = 8 es posible ya que es el mayor valor posible de M que satisface las condiciones necesarias.

Entrada: N = 5 
Salida: 3 
(5 XOR 4) = 1, por lo que M = 4 no es posible porque 1 no es un número par. 
(5 XOR 3) = 6, por lo que M = 3 es posible ya que 6 es un número par y 3 es el mayor valor posible de M (que es menor que N). 
 

Enfoque: Se 
deben hacer las siguientes observaciones mientras se resuelve el problema: 

• Un número impar representado en su forma binaria tiene 1 como su bit menos significativo (LSB), mientras que un número par representado en su forma binaria tiene 0 como su bit menos significativo (LSB).
• Al realizar la operación XOR , si el número de bits establecidos es impar, el valor XOR será 1. Si el número de bits establecidos es par, el valor XOR será 0.
• Por lo tanto, necesitamos realizar XOR de dos números impares o dos números pares para obtener un número par como resultado.

A partir de la explicación anterior, el problema se puede resolver mediante los siguientes pasos: 

1. Si N es impar, el mayor número impar menor que N será N – 2 .
2. Si N es par, el mayor número par menor que N será N – 2 .
3. Por lo tanto, si N = 1, imprima -1 como una M adecuada no se puede obtener en este caso. Para todos los demás casos, escriba N – 2 como respuesta.

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

// C++ program for the above problem.
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the maximum
// possible value of M
int getM(int n)
{
    // Edge case
    if (n == 1)
        return -1;
 
    // M = N - 2 is maximum
    // possible value
    else
        return n - 2;
}
 
// Driver Code
int main()
{
    int n = 10;
 
    int ans = getM(n);
    cout << ans;
}

// Java program for the above problem.
import java.util.*;
 
class GFG{
     
// Function to find the maximum
// possible value of M
static int getM(int n)
{
     
    // Edge case
    if (n == 1)
        return -1;
             
    // M = N - 2 is maximum
    // possible value
    else
        return n - 2;
}
     
// Driver code
public static void main(String[] args)
{
    int n = 10;
         
    System.out.print(getM(n));
}
}
 
// This code is contributed by sanjoy_62

# Python3 program for the above problem
 
# Function to find the maximum
# possible value of M
def getM(n):
     
    # Edge case
    if (n == 1):
        return -1;
         
    # M = N - 2 is maximum
    # possible value
    else:
        return n - 2;                
 
# Driver code
n = 10
 
print(getM(n))
 
# This code is contributed by sanjoy_62

// C# program for the above problem.
using System;
class GFG{
     
// Function to find the maximum
// possible value of M
static int getM(int n)
{
     
    // Edge case
    if (n == 1)
        return -1;
                 
    // M = N - 2 is maximum
    // possible value
    else
        return n - 2;
}
 
// Driver code
static void Main()
{
    int n = 10;
         
    Console.Write(getM(n));
}
}
 
// This code is contributed by divyeshrabadiya07

<script>
 
// Javascript program for the above problem.
 
// Function to find the maximum
// possible value of M
function getM(n)
{
        // Edge case
    if (n == 1)
        return -1;
         
    // M = N - 2 is maximum
    // possible value
    else
        return n - 2;
}
     
// Driver code
var n = 10;
 
document.write(getM(n));
 
// This code is contributed by Khushboogoyal499
    
</script>

8

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