Dada una array arr[] de tamaño N y un número entero K , la tarea es contar el número de pares de la array dada de modo que el XOR bit a bit de cada par sea mayor que K .
Ejemplos:
Entrada: arr = {1, 2, 3, 5} , K = 2
Salida: 4
Explicación:
XOR bit a bit de todos los pares posibles que satisfacen las condiciones dadas son:
arr[0] ^ arr[1] = 1 ^ 2 = 3
arr[0] ^ arr[3] = 1 ^ 5 = 4
arr[1] ^ arr[3] = 2 ^ 5 = 7
arr[0] ^ arr[3] = 3 ^ 5 = 6
Por lo tanto, la salida requerida es 4Entrada: arr[] = {3, 5, 6,8}, K = 2
Salida: 6
Enfoque ingenuo: el enfoque más simple para resolver este problema es atravesar la array dada y generar todos los pares posibles de la array dada y, para cada par, verificar si el XOR bit a bit del par es mayor que K o no. Si se encuentra que es cierto, entonces incremente el conteo de pares que tengan un XOR bit a bit mayor que K . Finalmente, imprima el conteo de dichos pares obtenidos.
Tiempo Complejidad :O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el problema se puede resolver usando Trie . La idea es iterar sobre la array dada y para cada elemento de la array, contar la cantidad de elementos presentes en el Trie cuyo XOR bit a bit con el elemento actual es mayor que K e insertar la representación binaria del elemento actual en el Trie . Finalmente, imprima el conteo de pares que tienen XOR bit a bit mayor que K . Siga los pasos a continuación para resolver el problema:
- Cree un Trie que tenga un Node raíz, digamos raíz para almacenar la representación binaria de cada elemento de la array dada.
- Recorra la array dada y cuente el número de elementos presentes en el Trie cuyo XOR bit a bit con el elemento actual es mayor que K e inserte la representación binaria del elemento actual .
- Finalmente, imprime el conteo de pares que satisface la condición dada.
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;
// Structure of Trie
struct TrieNode
{
// Stores binary representation
// of numbers
TrieNode *child[2];
// Stores count of elements
// present in a node
int cnt;
// Function to initialize
// a Trie Node
TrieNode() {
child[0] = child[1] = NULL;
cnt = 0;
}
};
// Function to insert a number into Trie
void insertTrie(TrieNode *root, int N) {
// Traverse binary representation of X.
for (int i = 31; i >= 0; i--) {
// Stores ith bit of N
bool x = (N) & (1 << i);
// Check if an element already
// present in Trie having ith bit x.
if(!root->child[x]) {
// Create a new node of Trie.
root->child[x] = new TrieNode();
}
// Update count of elements
// whose ith bit is x
root->child[x]->cnt+= 1;
// Update root.
root= root->child[x];
}
}
// Function to count elements
// in Trie whose XOR with N
// exceeds K
int cntGreater(TrieNode * root,
int N, int K)
{
// Stores count of elements
// whose XOR with N exceeding K
int cntPairs = 0;
// Traverse binary representation
// of N and K in Trie
for (int i = 31; i >= 0 &&
root; i--) {
// Stores ith bit of N
bool x = N & (1 << i);
// Stores ith bit of K
bool y = K & (1 << i);
// If the ith bit of K is 1
if (y) {
// Update root.
root =
root->child[1 - x];
}
// If the ith bit of K is 0
else{
// If an element already
// present in Trie having
// ith bit (1 - x)
if (root->child[1 - x]) {
// Update cntPairs
cntPairs +=
root->child[1 - x]->cnt;
}
// Update root.
root = root->child[x];
}
}
return cntPairs;
}
// Function to count pairs that
// satisfy the given conditions.
int cntGreaterPairs(int arr[], int N,
int K) {
// Create root node of Trie
TrieNode *root = new TrieNode();
// Stores count of pairs that
// satisfy the given conditions
int cntPairs = 0;
// Traverse the given array.
for(int i = 0;i < N; i++){
// Update cntPairs
cntPairs += cntGreater(root,
arr[i], K);
// Insert arr[i] into Trie.
insertTrie(root, arr[i]);
}
return cntPairs;
}
//Driver code
int main()
{
int arr[] = {3, 5, 6, 8};
int K= 2;
int N = sizeof(arr) / sizeof(arr[0]);
cout<<cntGreaterPairs(arr, N, K);
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Structure of Trie
static class TrieNode
{
// Stores binary representation
// of numbers
TrieNode []child = new TrieNode[2];
// Stores count of elements
// present in a node
int cnt;
// Function to initialize
// a Trie Node
TrieNode()
{
child[0] = child[1] = null;
cnt = 0;
}
};
// Function to insert a number
// into Trie
static void insertTrie(TrieNode root,
int N)
{
// Traverse binary representation
// of X.
for (int i = 31; i >= 0; i--)
{
// Stores ith bit of N
int x = (N) & (1 << i);
// Check if an element already
// present in Trie having ith
// bit x.
if (x < 2 && root.child[x] == null)
{
// Create a new node of Trie.
root.child[x] = new TrieNode();
}
// Update count of elements
// whose ith bit is x
if(x < 2 && root.child[x] != null)
root.child[x].cnt += 1;
// Update root.
if(x < 2)
root = root.child[x];
}
}
// Function to count elements
// in Trie whose XOR with N
// exceeds K
static int cntGreater(TrieNode root,
int N, int K)
{
// Stores count of elements
// whose XOR with N exceeding K
int cntPairs = 1;
// Traverse binary representation
// of N and K in Trie
for (int i = 31; i >= 0 &&
root!=null; i--)
{
// Stores ith bit of N
int x = N & (1 << i);
// Stores ith bit of K
int y = K & (1 << i);
// If the ith bit of K is 1
if (y == 1)
{
// Update root.
root = root.child[1 - x];
}
// If the ith bit of K is 0
else
{
// If an element already
// present in Trie having
// ith bit (1 - x)
if (x < 2 &&
root.child[1 - x] != null)
{
// Update cntPairs
cntPairs += root.child[1 - x].cnt;
}
// Update root.
if(x < 2)
root = root.child[x];
}
}
return cntPairs;
}
// Function to count pairs that
// satisfy the given conditions.
static int cntGreaterPairs(int arr[],
int N, int K)
{
// Create root node of Trie
TrieNode root = new TrieNode();
// Stores count of pairs that
// satisfy the given conditions
int cntPairs = 0;
// Traverse the given array.
for (int i = 0; i < N; i++)
{
// Update cntPairs
cntPairs += cntGreater(root,
arr[i], K);
// Insert arr[i] into Trie.
insertTrie(root, arr[i]);
}
return cntPairs;
}
// Driver code
public static void main(String[] args)
{
int arr[] = {3, 5, 6, 8};
int K = 2;
int N = arr.length;
System.out.print(cntGreaterPairs(arr,
N, K));
}
}
// This code is contributed by shikhasingrajput
Python3
# Python3 program to implement # the above approach # Structure of Trie class TrieNode: # Function to initialize # a Trie Node def __init__(self): self.child = [None, None] self.cnt = 0 # Function to insert a number into Trie def insertTrie(root, N): # Traverse binary representation of X. for i in range(31, -1, -1): # Stores ith bit of N x = bool((N) & (1 << i)) # Check if an element already # present in Trie having ith bit x. if (root.child[x] == None): # Create a new node of Trie. root.child[x] = TrieNode() # Update count of elements # whose ith bit is x root.child[x].cnt += 1 # Update root root= root.child[x] # Function to count elements # in Trie whose XOR with N # exceeds K def cntGreater(root, N, K): # Stores count of elements # whose XOR with N exceeding K cntPairs = 0 # Traverse binary representation # of N and K in Trie for i in range(31, -1, -1): if (root == None): break # Stores ith bit of N x = bool(N & (1 << i)) # Stores ith bit of K y = K & (1 << i) # If the ith bit of K is 1 if (y != 0): # Update root root = root.child[1 - x] # If the ith bit of K is 0 else: # If an element already # present in Trie having # ith bit (1 - x) if (root.child[1 - x]): # Update cntPairs cntPairs += root.child[1 - x].cnt # Update root root = root.child[x] return cntPairs # Function to count pairs that # satisfy the given conditions. def cntGreaterPairs(arr, N, K): # Create root node of Trie root = TrieNode() # Stores count of pairs that # satisfy the given conditions cntPairs = 0 # Traverse the given array. for i in range(N): # Update cntPairs cntPairs += cntGreater(root, arr[i], K) # Insert arr[i] into Trie. insertTrie(root, arr[i]) return cntPairs # Driver code if __name__=='__main__': arr = [ 3, 5, 6, 8 ] K = 2 N = len(arr) print(cntGreaterPairs(arr, N, K)) # This code is contributed by rutvik_56
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Structure of Trie
public class TrieNode
{
// Stores binary representation
// of numbers
public TrieNode []child = new TrieNode[2];
// Stores count of elements
// present in a node
public int cnt;
// Function to initialize
// a Trie Node
public TrieNode()
{
child[0] = child[1] = null;
cnt = 0;
}
};
// Function to insert a number
// into Trie
static void insertTrie(TrieNode root,
int N)
{
// Traverse binary representation
// of X.
for(int i = 31; i >= 0; i--)
{
// Stores ith bit of N
int x = (N) & (1 << i);
// Check if an element already
// present in Trie having ith
// bit x.
if (x < 2 && root.child[x] == null)
{
// Create a new node of Trie.
root.child[x] = new TrieNode();
}
// Update count of elements
// whose ith bit is x
if(x < 2 && root.child[x] != null)
root.child[x].cnt += 1;
// Update root.
if(x < 2)
root = root.child[x];
}
}
// Function to count elements
// in Trie whose XOR with N
// exceeds K
static int cntGreater(TrieNode root,
int N, int K)
{
// Stores count of elements
// whose XOR with N exceeding K
int cntPairs = 1;
// Traverse binary representation
// of N and K in Trie
for(int i = 31; i >= 0 &&
root != null; i--)
{
// Stores ith bit of N
int x = N & (1 << i);
// Stores ith bit of K
int y = K & (1 << i);
// If the ith bit of K is 1
if (y == 1)
{
// Update root.
root = root.child[1 - x];
}
// If the ith bit of K is 0
else
{
// If an element already
// present in Trie having
// ith bit (1 - x)
if (x < 2 &&
root.child[1 - x] != null)
{
// Update cntPairs
cntPairs += root.child[1 - x].cnt;
}
// Update root.
if(x < 2)
root = root.child[x];
}
}
return cntPairs;
}
// Function to count pairs that
// satisfy the given conditions.
static int cntGreaterPairs(int []arr,
int N, int K)
{
// Create root node of Trie
TrieNode root = new TrieNode();
// Stores count of pairs that
// satisfy the given conditions
int cntPairs = 0;
// Traverse the given array.
for(int i = 0; i < N; i++)
{
// Update cntPairs
cntPairs += cntGreater(root,
arr[i], K);
// Insert arr[i] into Trie.
insertTrie(root, arr[i]);
}
return cntPairs;
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 3, 5, 6, 8 };
int K = 2;
int N = arr.Length;
Console.Write(cntGreaterPairs(arr,
N, K));
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// Javascript program to implement
// the above approach
// Structure of Trie
class TrieNode
{
constructor()
{
this.child = new Array(2);
this.child[0] = this.child[1] = null;
this.cnt = 0;
}
}
// Function to insert a number
// into Trie
function insertTrie(root,N)
{
// Traverse binary representation
// of X.
for (let i = 31; i >= 0; i--)
{
// Stores ith bit of N
let x = (N) & (1 << i);
// Check if an element already
// present in Trie having ith
// bit x.
if (x < 2 && root.child[x] == null)
{
// Create a new node of Trie.
root.child[x] = new TrieNode();
}
// Update count of elements
// whose ith bit is x
if(x < 2 && root.child[x] != null)
root.child[x].cnt += 1;
// Update root.
if(x < 2)
root = root.child[x];
}
}
// Function to count elements
// in Trie whose XOR with N
// exceeds K
function cntGreater(root, N, K)
{
// Stores count of elements
// whose XOR with N exceeding K
let cntPairs = 1;
// Traverse binary representation
// of N and K in Trie
for (let i = 31; i >= 0 &&
root!=null; i--)
{
// Stores ith bit of N
let x = N & (1 << i);
// Stores ith bit of K
let y = K & (1 << i);
// If the ith bit of K is 1
if (y == 1)
{
// Update root.
root = root.child[1 - x];
}
// If the ith bit of K is 0
else
{
// If an element already
// present in Trie having
// ith bit (1 - x)
if (x < 2 &&
root.child[1 - x] != null)
{
// Update cntPairs
cntPairs += root.child[1 - x].cnt;
}
// Update root.
if(x < 2)
root = root.child[x];
}
}
return cntPairs;
}
// Function to count pairs that
// satisfy the given conditions.
function cntGreaterPairs(arr,N,K)
{
// Create root node of Trie
let root = new TrieNode();
// Stores count of pairs that
// satisfy the given conditions
let cntPairs = 0;
// Traverse the given array.
for (let i = 0; i < N; i++)
{
// Update cntPairs
cntPairs += cntGreater(root,
arr[i], K);
// Insert arr[i] into Trie.
insertTrie(root, arr[i]);
}
return cntPairs;
}
// Driver code
let arr=[3, 5, 6, 8];
let K = 2;
let N = arr.length;
document.write(cntGreaterPairs(arr,N, K));
// This code is contributed by patel2127
</script>
Producción:
6
Tiempo Complejidad :O(N * 32)
Espacio Auxiliar: O(N * 32)