Dado un número entero N (que siempre es una potencia de 2) que denota la longitud de una array que contiene números enteros en el rango [0, N-1] exactamente una vez, la tarea es emparejar estos elementos de tal manera que la suma de Y del par es igual a K. es decir, ∑ (a i & b i ) = K.
Nota: Cada elemento puede ser parte de un solo par.
Ejemplos:
Entrada: N = 4, K = 2
Salida: [[0, 1], [2, 3]]
Explicación: Aquí N = 4 significa que la array contiene arr[] = {0, 1, 2, 3},
Pares = [ 0, 1] y [2, 3]
(0 y 1) + (2 y 3) = 0 + 2 = 2.Entrada: N = 8, K = 4
Salida: [[4, 7], [1, 6], [2, 5], [0, 3]]
Planteamiento: La solución al problema se basa en la siguiente observación:
Puede haber cuatro casos como se muestra a continuación:
- Caso 1 (Si K = 0):
- Como N es potencia de 2, los pares de la forma {0+i, N-1-i} siempre tendrán AND bit a bit como 0 [donde i = 0 a (N-1)/2].
- Aquí AND de cada par será 0, lo que implica que la suma de cada par AND será 0.
- Después de eso, para K = 0, forme estos pares de la siguiente forma: [[0, N-1], [1, N-2] . . .].
- Caso 2 (Si K > 0 y K < N-1):
- AND bit a bit de K con N-1 es siempre K.
- De los pares anteriores, intercambiar solo elementos de dos pares y formar pares [K, N-1] y [0, el que era un par de K]. Entonces el AND será K.
- Caso 3 (Si K = N-1 y N = 4):
- En este caso no es posible el emparejamiento print -1.
- Caso 4 (Si K = N-1 y N > 4):
- El AND máximo de cualquier par puede ser N-2 que puede estar formado por N-1 y N-2. Entonces, se pueden formar otros dos pares para tener AND bit a bit = 1, es decir, (N-3 con 1) y (0 con 2) porque N-3 y 1 siempre son impares. Los otros pares se pueden mantener como estaban en el caso-1. Entonces, la suma AND bit a bit total será N-1.
Siga los pasos que se mencionan a continuación:
- Compruebe los valores de K y N.
- Forme las parejas como en el caso mencionado anteriormente según los valores de N y K.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to implement the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to print N-1 Pairs
void pairOfAND(int N, int K)
{
// Initializing ans which contains
// AND pairs having sum equal to K
vector<vector<int> > ans;
// Case 1 and Case 2
if (K >= 0 || K < N - 1) {
// Hash Map contains pairs
map<int, int> pair;
for (int i = 0, j = N - 1; i < N / 2; i++, j--) {
pair.insert({ i, j });
pair.insert({ j, i });
}
// Case 1
if (K == 0) {
for (int i = 0; i < N / 2; i++) {
vector<int> al;
al.push_back(i);
al.push_back(pair[i]);
ans.push_back(al);
}
}
// Case 2
else if (K < N / 2) {
vector<int> al;
al.push_back(K);
al.push_back(N - 1);
ans.push_back(al);
for (int i = 1; i < N / 2; i++) {
al = {};
al.push_back((i == K) ? 0 : i);
al.push_back(pair[i]);
ans.push_back(al);
}
}
else {
vector<int> al;
al.push_back(K);
al.push_back(N - 1);
ans.push_back(al);
for (int i = N / 2; i < N - 1; i++) {
al = {};
al.push_back((i == K) ? 0 : i);
al.push_back(pair[i]);
ans.push_back(al);
}
}
}
// Case 4
else {
if (N != 4) {
vector<int> al;
al.push_back(N - 1);
al.push_back(N - 2);
ans.push_back(al);
al = {};
al.push_back(N - 3);
al.push_back(1);
ans.push_back(al);
al = {};
al.push_back(0);
al.push_back(2);
ans.push_back(al);
for (int i = 3; i < N / 2; i++) {
al = {};
int comp = i ^ (N - 1);
al.push_back(i);
al.push_back(comp);
ans.push_back(al);
}
}
}
// Case 3
if (ans.size() == 0)
cout << (-1);
else
for (auto arr : ans) {
for (auto dt : arr)
cout << dt << " ";
cout << "\n";
}
}
// Driver Code
int main()
{
int N = 4;
int K = 2;
pairOfAND(N, K);
return 0;
}
// This code is contributed by rakeshsahnis
Java
// Java code to implement the above approach
import java.util.*;
class GFG {
// Function to print N-1 Pairs
public static void pairOfAND(int N,
int K)
{
// Initializing ans which contains
// AND pairs having sum equal to K
List<List<Integer> > ans
= new ArrayList<>();
// Case 1 and Case 2
if (K >= 0 || K < N - 1) {
// Hash Map contains pairs
Map<Integer, Integer> pair
= new HashMap<>();
for (int i = 0, j = N - 1;
i < N / 2;
i++, j--) {
pair.put(i, j);
pair.put(j, i);
}
// Case 1
if (K == 0) {
for (int i = 0; i < N / 2;
i++) {
List<Integer> al
= new ArrayList<>();
al.add(i);
al.add(pair.get(i));
ans.add(al);
}
}
// Case 2
else if (K < N / 2) {
List<Integer> al
= new ArrayList<>();
al.add(K);
al.add(N - 1);
ans.add(al);
for (int i = 1; i < N / 2;
i++) {
al = new ArrayList<>();
al.add((i == K) ? 0 : i);
al.add(pair.get(i));
ans.add(al);
}
}
else {
List<Integer> al
= new ArrayList<>();
al.add(K);
al.add(N - 1);
ans.add(al);
for (int i = N / 2; i < N - 1;
i++) {
al = new ArrayList<>();
al.add((i == K) ? 0 : i);
al.add(pair.get(i));
ans.add(al);
}
}
}
// Case 4
else {
if (N != 4) {
List<Integer> al
= new ArrayList<>();
al.add(N - 1);
al.add(N - 2);
ans.add(al);
al = new ArrayList<>();
al.add(N - 3);
al.add(1);
ans.add(al);
al = new ArrayList<>();
al.add(0);
al.add(2);
ans.add(al);
for (int i = 3; i < N / 2;
i++) {
al = new ArrayList<>();
int comp = i ^ (N - 1);
al.add(i);
al.add(comp);
ans.add(al);
}
}
}
// Case 3
if (ans.isEmpty())
System.out.println(-1);
else
System.out.println(ans);
}
// Driver Code
public static void main(String[] args)
{
int N = 4;
int K = 2;
pairOfAND(N, K);
}
}
Producción
[[2, 3], [0, 1]]
Complejidad temporal: O(N)
Espacio auxiliar: O(N)