Dada una array arr[] que consta de N enteros y un entero K , la tarea es contar el número de pares que satisfacen la ecuación 2*(arr[i] & arr[j]) + (arr[i] ^ arr[j ]) = k.
Ejemplos:
Entrada: arr[] = {1, 5, 4, 8, 7}, K = 9
Salida: 2
Explicación:
- Elementos en el índice 0 y 3, es decir, arr[i] = 1, arr[j] = 8, satisface las ecuaciones dadas.
- Los elementos en el índice 1 y 2, es decir, arr[i] = 5, arr[j] = 4, satisfacen las ecuaciones dadas.
Entrada: arr[] = {1, 2, 2, 4, 5}, K = 3
Salida: 2
Enfoque ingenuo: el enfoque más simple es generar todos los pares posibles a partir de la array y, para cada par, verificar si el par satisface la ecuación dada o no.
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar en función de las siguientes observaciones:
Observación:
A + B = (A ^ B) + 2 * (A y B)
Al calcular la suma, si ambos bits son 1 (es decir, AND es 1), el bit resultante es 0 y 1 se agrega como acarreo, lo que significa que cada bit en AND se desplaza a la izquierda por 1 , es decir, el valor de AND se multiplica por 2 y añadido.
Por lo tanto, A + B = ecuaciones dadas.
Por lo tanto, esto verifica la observación anterior.
Siga los pasos a continuación para resolver el problema:
- El problema ahora se reduce a un problema de dos sumas y la tarea se reduce a contar pares cuya suma es igual a K.
- Inicialice un mapa_desordenado , digamos mp , y una variable, digamos cnt , para contar el número de pares que satisfacen las condiciones dadas.
- Atraviesa la array y para cada elemento:
- Si mp[K – arr[i]] no es cero, entonces agregue su valor a cnt .
- Actualiza la frecuencia de arr[i] en Map .
- Imprime el cnt como la respuesta.
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 count number of pairs
// satisfying the given conditions
void countPairs(int arr[], int N, int K)
{
// Stores the frequency of array elements
unordered_map<int, int> mp;
// Stores the total number of pairs
int cnt = 0;
// Traverse the array
for (int i = 0; i < N; i++) {
// Add it to cnt
cnt += mp[K - arr[i]];
// Update frequency of
// current array element
mp[arr[i]]++;
}
// Print the count
cout << cnt;
}
// Driver Code
int main()
{
// Given array
int arr[] = { 1, 5, 4, 8, 7 };
// Size of the array
int N = sizeof(arr) / sizeof(arr[0]);
// Given value of K
int K = 9;
countPairs(arr, N, K);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG
{
// Function to count number of pairs
// satisfying the given conditions
static void countPairs(int arr[], int N, int K)
{
// Stores the frequency of array elements
Map<Integer, Integer> mp = new HashMap<>();
// Stores the total number of pairs
int cnt = 0;
// Traverse the array
for (int i = 0; i < N; i++)
{
// Add it to cnt
if (mp.get(K - arr[i]) != null)
cnt += mp.get(K - arr[i]);
// Update frequency of
// current array element
mp.put(arr[i], mp.get(arr[i]) == null
? 1
: mp.get(arr[i]) + 1);
}
// Print the count
System.out.println(cnt);
}
// Driver Code
public static void main(String[] args)
{
// Given array
int arr[] = { 1, 5, 4, 8, 7 };
// Size of the array
int N = arr.length;
// Given value of K
int K = 9;
countPairs(arr, N, K);
}
}
// This code is contributed by Dharanendra L V
Python3
# Python3 program for the above approach from collections import defaultdict # Function to count number of pairs # satisfying the given conditions def countPairs(arr, N, K) : # Stores the frequency of array elements mp = defaultdict(int) # Stores the total number of pairs cnt = 0 # Traverse the array for i in range(N): # Add it to cnt cnt += mp[K - arr[i]] # Update frequency of # current array element mp[arr[i]] += 1 # Print the count print(cnt) # Driver Code # Given array arr = [ 1, 5, 4, 8, 7 ] # Size of the array N = len(arr) # Given value of K K = 9 countPairs(arr, N, K) # This code is contributed by sanjoy_62.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG
{
// Function to count number of pairs
// satisfying the given conditions
static void countPairs(int[] arr, int N, int K)
{
// Stores the frequency of array elements
Dictionary<int, int> mp
= new Dictionary<int, int>();
// Stores the total number of pairs
int cnt = 0;
// Traverse the array
for (int i = 0; i < N; i++) {
// Add it to cnt
if (mp.ContainsKey(K - arr[i]))
cnt += mp[K - arr[i]];
// Update frequency of
// current array element
if (mp.ContainsKey(arr[i])) {
var val = mp[arr[i]];
mp.Remove(arr[i]);
mp.Add(arr[i], val + 1);
}
else {
mp.Add(arr[i], 1);
}
}
// Print the count
Console.WriteLine(cnt);
}
// Driver Code
static public void Main()
{
// Given array
int[] arr = { 1, 5, 4, 8, 7 };
// Size of the array
int N = arr.Length;
// Given value of K
int K = 9;
countPairs(arr, N, K);
}
}
// This code is contributed by Dharanendra L V
Javascript
<script>
// JavaScript program for the above approach
// Function to count number of pairs
// satisfying the given conditions
function countPairs(arr,N,K)
{
// Stores the frequency of array elements
let mp = new Map();
// Stores the total number of pairs
let cnt = 0;
// Traverse the array
for (let i = 0; i < N; i++) {
// Add it to cnt
if(mp.has(K - arr[i]))
{
cnt += mp.get(K - arr[i]);
}
// Update frequency of
// current array element
if(mp.has(arr[i]))
{
mp.set(arr[i], mp.get(arr[i]) + 1);
}
else{
mp.set(arr[i], 1);
}
}
// Print the count
document.write(cnt);
}
// Driver Code
// Given array
let arr = [ 1, 5, 4, 8, 7 ];
// Size of the array
let N = arr.length;
// Given value of K
let K = 9;
countPairs(arr, N, K);
</script>
2
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por shubhampokhriyal2018 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA