Dado un número entero N , la tarea es encontrar todos los pares no negativos (A, B) tales que la suma de Bitwise OR y Bitwise AND de A , B sea igual a N , es decir, (A | B) + (A & B) = norte .
Ejemplos:
Entrada: N = 5
Salida: (0, 5), (1, 4), (2, 3), (3, 2), (4, 1), (5, 0)
Explicación: Todos los pares posibles que satisfacen las necesidades condiciones:
- (0 | 5) + (0 y 5) = 5 + 0 = 5
- (1 | 4) + (1 y 4) = 5 + 0 = 5
- (2 | 3) + (2 y 3) = 3 + 2 = 5
- (3 | 2) + (3 y 2) = 3 + 2 = 5
- (4 | 1) + (4 y 1) = 5 + 0 = 5
- (5 | 0) + (5 y 0) = 5 + 0 = 5
Entrada: N = 7
Salida: (0, 7), (1, 6), (2, 5), (3, 4), (4, 3), (5, 2), (6, 1), ( 7, 0)
Explicación: Todos los pares posibles que cumplan las condiciones necesarias:
- (0 | 7) + (0 y 7) = 7 + 0 =7
- (1 | 6) + (1 y 6) = 7 + 0 =7
- (2 | 5) + (2 y 5) = 7 + 0 =7
- (3 | 4) + (3 y 4) = 7 + 0 =7
- (4 | 3) + (4 y 3) = 7 + 0 =7
- (5 | 2) + (5 y 2) = 7 + 0 =7
- (6 | 1) + (6 y 1) = 7 + 0 = 7
- (7 | 0) + (7 y 0) = 7 + 0 = 7
Enfoque ingenuo: el enfoque más simple es iterar sobre el rango [0, N] e imprimir esos pares (A, B) que satisfacen la condición (A | B) + (A & B) = N .
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque Eficiente: Para optimizar el enfoque anterior, la idea se basa en la observación de que todos aquellos pares no negativos cuya suma es igual a N satisfacen la condición dada. Por lo tanto, itere sobre el rango [0, N] usando la variable i e imprima el par i y (N – i) .
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 print all pairs whose // sum of Bitwise OR and AND is N void findPairs(int N) { // Iterate from i = 0 to N for (int i = 0; i <= N; i++) { // Print pairs (i, N - i) cout << "(" << i << ", " << N - i << "), "; } } // Driver Code int main() { int N = 5; findPairs(N); return 0; }
Java
// Java program for the above approach import java.util.*; import java.lang.*; class GFG{ // Function to print all pairs whose // sum of Bitwise OR and AND is N static void findPairs(int N) { // Iterate from i = 0 to N for(int i = 0; i <= N; i++) { // Print pairs (i, N - i) System.out.print( "(" + i + ", " + (N - i) + "), "); } } // Driver code public static void main(String[] args) { int N = 5; findPairs(N); } } // This code is contributed by ajaykr00kj
Python3
# Python3 program for the above approach # Function to print all pairs whose # sum of Bitwise OR and AND is N def findPairs(N): # Iterate from i = 0 to N for i in range(0, N + 1): # Print pairs (i, N - i) print("(", i, ",", N - i, "), ", end = "") # Driver code if __name__ == "__main__": N = 5 findPairs(N) # This code is contributed by ajaykr00kj
C#
// C# program for the above approach using System; class GFG{ // Function to print all pairs whose // sum of Bitwise OR and AND is N static void findPairs(int N) { // Iterate from i = 0 to N for(int i = 0; i <= N; i++) { // Print pairs (i, N - i) Console.Write( "(" + i + ", " + (N - i) + "), "); } } // Driver code public static void Main() { int N = 5; findPairs(N); } } // This code is contributed by sanjoy_62
Javascript
<script> // JavaScript program for the above approach // Function to print all pairs whose // sum of Bitwise OR and AND is N function findPairs(N) { // Iterate from i = 0 to N for(let i = 0; i <= N; i++) { // Print pairs (i, N - i) document.write( "(" + i + ", " + (N - i) + "), "); } } // Driver Code let N = 5; findPairs(N); // This code is contributed by avijitmondal1998. </script>
(0, 5), (1, 4), (2, 3), (3, 2), (4, 1), (5, 0),
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por ajaykr00kj y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA