Dado un número entero N , la tarea es encontrar el número más grande M , donde ( M < N ), tal que N(XOR)M sea igual a N(OR)M , es decir , (N ^ M) = (N | M) .
Ejemplos:
Entrada: N = 5
Salida: 2
5 ^ 4 = 1 y 5 | 4 = 5. Por lo tanto, XOR y OR entre ellos no son iguales.
5^3 = 6 y 5 | 3 = 7. Por lo tanto, XOR y OR entre ellos no son iguales.
5^2 = 7 y 5 | 2 = 7. Por lo tanto, XOR y OR entre ellos son iguales.
Entrada: N = 14
Salida: 1
Enfoque:
para obtener el número M requerido , recorra todos los bits de N desde su bit menos significativo (LSB) hasta su bit más significativo (MSB). Aquí surgen dos casos:
- Si el i -ésimo bit de N es 1 entonces:
- Si el i -ésimo bit de M se establece en 1 , entonces N^M no será igual a N|M como (1^1 = 0) y (1|1 = 1) .
- Si el i -ésimo bit se establece de M a 0 , entonces N^M será igual a N|M como (1^0 = 1) y (1|0 = 1) .
- Entonces, si el i -ésimo bit de N es 1 , establezca el i -ésimo bit de M en 0 .
- Si el i -ésimo bit de N es 0 entonces:
- Si el i -ésimo bit de M se establece en 1 , entonces N^M será igual a N|M como ( 0^1 = 1 ) y ( 0|1 = 1 ).
- Si establecemos el i -ésimo bit de M en 0 , entonces N^M será igual a N|M como ( 0^0 = 0 ) y ( 0|0 = 0 ).
- Entonces, si el i -ésimo bit de M se establece en 0 o 1 , N^M siempre será igual a N|M .
- Como se debe encontrar el valor más grande de M que es menor que N , siempre establezca el i -ésimo bit de M en 1 .
Ilustración:
- norte = 5
- representación de 32 bits de 5 = 00000000000000000000000000000101
- Índice LSB de 5 = 31
- índice MSB de 5 = 29
- Pasando de LSB a MSB, es decir, de 31 a 29:
- Para el índice 31, N[31] = 1. Por lo tanto, M[31] debe establecerse en 0.
- Para el índice 30, N[30] = 0. Por lo tanto, M[30] debe establecerse en 1.
- Para el índice 29, N[29] = 1. Por lo tanto, M[29] debe establecerse en 0.
- Así, la representación de 32 bits de M es 000000000000000000000000000000010, que es igual a 2 en representación decimal.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to find required // number M int equalXORandOR(int n) { // Initialising m int m = 0; // Finding the index of the // 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 m; } // Driver Code int main() { int n = 14; cout << equalXORandOR(n); return 0; }
Java
// Java program to implement // the above approach class GFG{ // Function to find required // number M static int equalXORandOR(int n) { // Initialising m int m = 0; // Finding the index of the // 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 m; } // Driver Code public static void main(String[] args) { int n = 14; System.out.print(equalXORandOR(n)); } } // This code is contributed by amal kumar choubey
Python3
# Python3 program to implement # the above approach from math import log2 # Function to find required # number M def equalXORandOR(n): # Initialising m m = 0 # Finding the index of the # most significant bit of N MSB = int(log2(n)) # Calculating required number for i in range(MSB + 1): if(not(n & (1 << i))): m += (1 << i) return m # Driver Code n = 14 # Function call print(equalXORandOR(n)) # This code is contributed by Shivam Singh
C#
// C# program to implement // the above approach using System; class GFG{ // Function to find required // number M static int equalXORandOR(int n) { // Initialising m int m = 0; // Finding the index of the // 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 m; } // Driver Code public static void Main(String[] args) { int n = 14; Console.Write(equalXORandOR(n)); } } // This code is contributed by amal kumar choubey
Javascript
<script> // javascript program to implement // the above approach // Function to find required // number M function equalXORandOR(n) { // Initialising m var m = 0; // Finding the index of the // 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 m; } // Driver Code var n = 14; document.write(equalXORandOR(n)); // This code contributed by Rajput-Ji </script>
1
Complejidad de tiempo: O(log 2 N)
Espacio auxiliar: O(1)