Encuentre un número M < N tal que la diferencia entre su XOR y AND sea máxima

Dado un número natural N , la tarea es encontrar un número M más pequeño que N tal que la diferencia entre su bit a bit XOR ( N ^ M ) y bit a bit AND ( N & M ) sea máxima.
 

Ejemplos:

Entrada: N = 4
Salida: 3
Explicación:  
(4 ^ 0) – (4 y 0) = 4
(4 ^ 1) – (4 y 1) = 5
(4 ^ 2) – (4 y 2) = 6
( 4 ^ 3) – (4 y 3) = 7
Por lo tanto, el valor de M es 3.

Entrada: N = 6
Salida: 1
Explicación: 
La diferencia entre N ^ M y N & M es máxima cuando M = 1.

Enfoque ingenuo: la idea es iterar para cada elemento menor que N y encontrar M para el cual N^M – N&M es máximo. A continuación se muestran los pasos:
 

  • Inicialice una variable, digamos maxDiff con 0 y M con -1.
  • Iterar de 0 a N-1 y calcular diff = N^i -N&i .
  • Si diff es mayor o igual a maxDiff asigne M = i y maxDiff = diff.

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 to return M<N such that
// N^M - N&M is maximum
int getMaxDifference(int N)
{
    // Initialize variables
    int M = -1;
    int maxDiff = 0;
 
    // Iterate for all values < N
    for (int i = 0; i < N; i++) {
 
        // Find the difference between
        // Bitwise XOR and AND
        int diff = (N ^ i) - (N & i);
 
        // Check if new difference is
        // greater than previous maximum
        if (diff >= maxDiff) {
 
            // Update variables
            maxDiff = diff;
            M = i;
        }
    }
 
    // Return the answer
    return M;
}
 
// Driver Code
int main()
{
    // Given Number N
    int N = 6;
 
    // Function Call
    cout << getMaxDifference(N);
    return 0;
}

Java

// Java program for the above approach
class GFG{
 
// Function to return M<N such that
// N^M - N&M is maximum
static int getMaxDifference(int N)
{
    // Initialize variables
    int M = -1;
    int maxDiff = 0;
 
    // Iterate for all values < N
    for (int i = 0; i < N; i++)
    {
 
        // Find the difference between
        // Bitwise XOR and AND
        int diff = (N ^ i) - (N & i);
 
        // Check if new difference is
        // greater than previous maximum
        if (diff >= maxDiff)
        {
 
            // Update variables
            maxDiff = diff;
            M = i;
        }
    }
 
    // Return the answer
    return M;
}
 
// Driver Code
public static void main(String[] args)
{
    // Given Number N
    int N = 6;
 
    // Function Call
    System.out.print(getMaxDifference(N));
}
}
 
// This code is contributed by Rohit_ranjan

Python3

# Python3 program for the above approach
 
# Function to return M<N such that
# N^M - N&M is maximum
def getMaxDifference(N):
     
    # Initialize variables
    M = -1;
    maxDiff = 0;
 
    # Iterate for all values < N
    for i in range(N):
 
        # Find the difference between
        # Bitwise XOR and AND
        diff = (N ^ i) - (N & i);
 
        # Check if new difference is
        # greater than previous maximum
        if (diff >= maxDiff):
             
            # Update variables
            maxDiff = diff;
            M = i;
 
    # Return the answer
    return M;
 
# Driver Code
if __name__ == '__main__':
     
    # Given number N
    N = 6;
 
    # Function call
    print(getMaxDifference(N));
 
# This code is contributed by amal kumar choubey

C#

// C# program for the above approach
using System;
 
class GFG{
 
// Function to return M<N such that
// N^M - N&M is maximum
static int getMaxDifference(int N)
{
     
    // Initialize variables
    int M = -1;
    int maxDiff = 0;
 
    // Iterate for all values < N
    for(int i = 0; i < N; i++)
    {
         
        // Find the difference between
        // Bitwise XOR and AND
        int diff = (N ^ i) - (N & i);
 
        // Check if new difference is
        // greater than previous maximum
        if (diff >= maxDiff)
        {
             
            // Update variables
            maxDiff = diff;
            M = i;
        }
    }
 
    // Return the answer
    return M;
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Given number N
    int N = 6;
 
    // Function call
    Console.Write(getMaxDifference(N));
}
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
// javascript program for the above approach   
// Function to return M<N such that
    // N^M - N&M is maximum
    function getMaxDifference(N) {
        // Initialize variables
        var M = -1;
        var maxDiff = 0;
 
        // Iterate for all values < N
        for (i = 0; i < N; i++) {
 
            // Find the difference between
            // Bitwise XOR and AND
            var diff = (N ^ i) - (N & i);
 
            // Check if new difference is
            // greater than previous maximum
            if (diff >= maxDiff) {
 
                // Update variables
                maxDiff = diff;
                M = i;
            }
        }
 
        // Return the answer
        return M;
    }
 
    // Driver Code
     
        // Given Number N
        var N = 6;
 
        // Function Call
        document.write(getMaxDifference(N));
 
// This code contributed by aashish1995
</script>
Producción: 

1

 

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

Enfoque eficiente: la idea es observar que la diferencia entre Bitwise XOR y Bitwise AND es máxima si Bitwise AND de los dos números es el número mínimo posible y el número mínimo posible es 0
El AND bit a bit entre los dos números es cero si y solo si se complementan entre sí. Por lo tanto, el valor posible de M debe ser el complemento del número N dado .
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 to flip all bits of N
int findM(int N)
{
    int M = 0;
 
    // Finding most significant bit of N
    int MSB = (int)log2(N);
 
    // Calculating required number
    for (int i = 0; i < MSB; i++) {
 
        if (!(N & (1 << i)))
            M += (1 << i);
    }
 
    // Return the answer
    return M;
}
 
// Driver Code
int main()
{
    // Given Number
    int N = 6;
 
    // Function Call
    cout << findM(N);
    return 0;
}

Java

// Java program for the above approach
class GFG{
 
// Function to flip all bits of N
static int findM(int N)
{
    int M = 0;
 
    // Finding most significant bit of N
    int MSB = (int)Math.log(N);
 
    // Calculating required number
    for(int i = 0; i < MSB; i++)
    {
        if ((N & (1 << i)) == 0)
            M += (1 << i);
    }
 
    // Return the answer
    return M;
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given number
    int N = 6;
 
    // Function call
    System.out.print(findM(N));
}
}
 
// This code is contributed by Rajput-Ji

Python3

# Python3 program for the above approach
import math
 
# Function to flip all bits of N
def findM(N):
     
    M = 0;
 
    # Finding most significant bit of N
    MSB = int(math.log(N));
 
    # Calculating required number
    for i in range(MSB):
        if ((N & (1 << i)) == 0):
            M += (1 << i);
     
    # Return the answer
    return M;
 
# Driver Code
if __name__ == '__main__':
 
    # Given number
    N = 6;
 
    # Function call
    print(findM(N));
 
# This code is contributed by Amit Katiyar

C#

// C# program for the above approach
using System;
 
class GFG{
 
// Function to flip all bits of N
static int findM(int N)
{
    int M = 0;
 
    // Finding most significant bit of N
    int MSB = (int)Math.Log(N);
 
    // Calculating required number
    for(int i = 0; i < MSB; i++)
    {
        if ((N & (1 << i)) == 0)
            M += (1 << i);
    }
 
    // Return the answer
    return M;
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Given number
    int N = 6;
 
    // Function call
    Console.Write(findM(N));
}
}
 
// This code is contributed by Amit Katiyar

Javascript

<script>
// javascript program for the above approach   
// Function to flip all bits of N
    function findM(N) {
        var M = 0;
 
        // Finding most significant bit of N
        var MSB = parseInt( Math.log(N));
 
        // Calculating required number
        for (i = 0; i < MSB; i++) {
            if ((N & (1 << i)) == 0)
                M += (1 << i);
        }
 
        // Return the answer
        return M;
    }
 
    // Driver Code
     
        // Given number
        var N = 6;
 
        // Function call
        document.write(findM(N));
 
// This code is contributed by Rajput-Ji
</script>
Producción: 

1

 

Complejidad de tiempo: O(log 2 N) 
Espacio auxiliar: O(1)
 

Publicación traducida automáticamente

Artículo escrito por math_lover 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 *