Dado un entero positivo N, la tarea es encontrar todos los pares de enteros (i, j) del rango [1, N] en orden creciente de i tal que:
- 1 ≤ yo, j ≤ norte
- yo + j = norte
- yo + j = 2*(yo ^ j)
- Si no hay tales pares, devuelve un par {-1, -1}.
Nota:Aquí ‘^’ denota la operación XOR bit a bit .
Ejemplos:
Entrada: N = 4
Salida: {{1, 3}, {3, 1}}
Explicación: Un total de 3 pares satisfacen la primera condición: (1, 3), (2, 2), (3, 1).
Solo hay dos pares válidos de ellos: (1, 3) y (3, 1) como 1 + 3 = 4 = 2 * (1 ^ 3).Entrada: 7
Salida: {-1, -1}Entrada: 144
Salida: {{36, 108}, {44, 100}, {100, 44}, {108, 36 }}
Acercarse:
El problema puede verse como un problema de manipulación bit a bit que satisface las condiciones previas.
Si los pares suman N , entonces es obvio que el segundo elemento j del par se puede generar usando el primer elemento i como j = N – i . Entonces solo tenemos que verificar la condición restante i + j = 2 * (i ^ j).
Siga los pasos que se mencionan a continuación para resolver el problema:
- Recorra de 1 a N para el primer elemento i y el segundo elemento como j = N – i .
- Verifique que N = i + j y N = 2 * (i ^ j) e inserte los primeros elementos i y j en el vector 2-D ans e incremente el conteo .
- Devuelve {-1, -1} si cuenta = 0 o ans, si cuenta > 0.
A continuación se muestra la implementación del enfoque anterior.
C++14
// C++ code to solve using above approach #include <bits/stdc++.h> using namespace std; // Function to find the pair vector<vector<int> > solve(int& N) { vector<int> x, y; int count = 0; vector<vector<int> > ans; // For each element from 1 to N // check whether i + j = 2 * (i^j) // where j = N - i for (int i = 1; i <= N; i++) { int j = N - i; if (N == 2 * (i ^ j)) { // Insert the pair into answer ans.push_back({ i, j }); // Increase count accordingly count++; } } if (count == 0) return { { -1, -1 } }; return ans; } // Function to print the pairs void printPairs(int& N) { vector<vector<int> > ans = solve(N); for (auto& x : ans) { for (auto& y : x) cout << y << " "; cout << endl; } } // Driver code int main() { int N = 144; // Function call printPairs(N); return 0; }
36 108 44 100 100 44 108 36
Complejidad del tiempo:O(N)
Espacio Auxiliar:O(1)
Publicación traducida automáticamente
Artículo escrito por prophet1999 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA