El número más grande M que tiene un recuento de bits de N tal que se maximiza la diferencia entre su valor OR y XOR

Dado un número natural N , la tarea es encontrar el mayor número M que tenga la misma longitud en representación binaria que N tal que la diferencia entre N | M y N^M es máximo.

Ejemplos:

Entrada: N = 6
Salida: 7
Explicación:  
Todos los números que tienen la misma longitud en representación binaria que N son 4, 5, 6, 7.
(6 | 4) – (6 ^ 4) = 4
(6 | 5) – ( 6 ^ 5) = 4
(6 | 6) – (6 ^ 6) = 6
(6 | 7) – (6 ^ 7) = 6
Por lo tanto, el M más grande para el cual (N | M) – (N ^ M) es máximo es 7

Entrada: N = 10
Salida: 15
Explicación:  
El número más grande M = 15 que tiene la misma longitud en representación binaria que 10 y la diferencia entre N | M y N^M es máximo.

Enfoque ingenuo: la idea es simplemente encontrar todos los números que tengan la misma longitud en representación binaria como N y luego, para cada número, iterar y encontrar el entero más grande que tenga (N | i) – (N ^ i) máximo. 

Complejidad temporal: O(N)
Espacio auxiliar: O(1)

Enfoque eficiente: la idea es inicializar M = 0 e iterar bit a bit en N (digamos i ) y establecer o desactivar el i ^-ésimo bit de M de acuerdo con las siguientes 2 observaciones:

• Cuando se establece un i ^-ésimo bit de N : En este caso, si desactivamos el i ^-ésimo bit de M, el i ^-ésimo bit de ambos N | Se establecerán M y N^M , mientras que al establecer este bit de M, se establecerá un i ^-ésimo bit de N|M y N^M se desactivará, lo que aumentará (N | M) – (N ^ M) . Por lo tanto, es óptimo establecer este bit de M.
• Cuando un i ^-ésimo bit de N está desactivado: En este caso, si activamos este bit de M, tanto N|M como N^M tendrán este bit activado o al mantener este bit de M desactivado, tanto N|M como N^M tendrá este bit desactivado. Entonces, en este caso, no podemos aumentar la diferencia entre ellos, pero como el requisito es generar la máxima M posible, configure este bit de M .
• De las observaciones anteriores, está claro que M tendrá todos los bits establecidos.

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the largest number
// M having the same length in binary
// form as N such that the difference
// between N | M and N ^ M is maximum
int maxORminusXOR(int N)
{
    // Find the most significant
    // bit of N
    int MSB = log2(N);
 
    // Initialize M
    int M = 0;
 
    // Set all the bits of M
    for (int i = 0; i <= MSB; i++)
        M += (1 << i);
 
    // Return the answer
    return M;
}
 
// Driver Code
int main()
{
    // Given Number N
    int N = 10;
 
    // Function Call
    cout << maxORminusXOR(N);
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function to find the largest number
// M having the same length in binary
// form as N such that the difference
// between N | M and N ^ M is maximum
static int maxORminusXOR(int N)
{
     
    // Find the most significant
    // bit of N
    int MSB = (int)Math.ceil(Math.log(N));
 
    // Initialize M
    int M = 0;
 
    // Set all the bits of M
    for(int i = 0; i <= MSB; i++)
        M += (1 << i);
 
    // Return the answer
    return M;
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given number N
    int N = 10;
 
    // Function call
    System.out.print(maxORminusXOR(N));
}
}
 
// This code is contributed by Rajput-Ji

# Python3 program for the above approach
import math
 
# Function to find the largest number
# M having the same length in binary
# form as N such that the difference
# between N | M and N ^ M is maximum
def maxORminusXOR(N):
 
    # Find the most significant
    # bit of N
    MSB = int(math.log2(N));
 
    # Initialize M
    M = 0
 
    # Set all the bits of M
    for i in range(MSB + 1):
        M += (1 << i)
 
    # Return the answer
    return M
 
# Driver code
if __name__ == '__main__':
     
    # Given Number N
    N = 10
 
    # Function call
    print(maxORminusXOR(N))
 
# This code is contributed by jana_sayantan

// C# program for the above approach
using System;
 
class GFG{
 
// Function to find the largest number
// M having the same length in binary
// form as N such that the difference
// between N | M and N ^ M is maximum
static int maxORminusXOR(int N)
{
     
    // Find the most significant
    // bit of N
    int MSB = (int)Math.Ceiling(Math.Log(N));
 
    // Initialize M
    int M = 0;
 
    // Set all the bits of M
    for(int i = 0; i <= MSB; i++)
        M += (1 << i);
 
    // Return the answer
    return M;
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Given number N
    int N = 10;
 
    // Function call
    Console.Write(maxORminusXOR(N));
}
}
 
// This code is contributed by 29AjayKumar

<script>
 
// JavaScript implementation of the above approach
  
// Function to find the largest number
// M having the same length in binary
// form as N such that the difference
// between N | M and N ^ M is maximum
function maxORminusXOR(N)
{
       
    // Find the most significant
    // bit of N
    let MSB = Math.ceil(Math.log(N));
   
    // Initialize M
    let M = 0;
   
    // Set all the bits of M
    for(let i = 0; i <= MSB; i++)
        M += (1 << i);
   
    // Return the answer
    return M;
}
 
// Driver code
         
    // Given number N
    let N = 10;
   
    // Function call
    document.write(maxORminusXOR(N));
   
  // This code is contributed by code_hunt.
</script>

15

Complejidad temporal: O(log N)
Espacio auxiliar: O(1)