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