Dada una array de N enteros y un entero K . La tarea es imprimir el número máximo de pares (a[i]+a[j]) posibles que sean divisibles por K.
Nota : un número de índice particular no puede considerarse en más de un par.
Ejemplos:
Entrada: a[] = {1, 2, 2, 3, 2, 4, 10}, k =2
Salida: 3
Los pares son: (1, 2), (4, 5), (0, 3)
Entrada : a[] = {1, 2, 2, 3, 2, 4, 5}, k = 3
Salida: 2
Enfoque ingenuo : un enfoque ingenuo es iterar usando dos bucles y calcular el número total de pares cuya suma es divisible por K.
Complejidad de tiempo: O (N ^ 2), ya que usaremos bucles anidados para atravesar N * N veces. Donde N es el número de elementos de la array.
Espacio auxiliar: O(1), ya que no usaremos ningún espacio adicional.
Enfoque eficiente : un enfoque eficiente será utilizar una técnica de hashing para resolver el problema. Se pueden seguir los siguientes pasos para resolver el problema anterior.
- Inicialmente, aumente el hash[a[i]%k] en uno para cada elemento de la array.
- Iterar en el mapa y obtener todos los valores hash posibles.
- Si el valor hash es 0, entonces el número de pares será hash[0]/2.
- Después de eso, para cada valor hash x, podemos usar el mínimo de (hash[x], hash[kx]) y usarlos para crear pares.
- Reste el número de pares utilizados del valor hash en consecuencia.
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;
// Function to maximize the number of pairs
int findMaximumPairs(int a[], int n, int k)
{
// Hash-table
unordered_map<int, int> hash;
for (int i = 0; i < n; i++)
hash[a[i] % k]++;
int count = 0;
// Iterate for all numbers less than hash values
for (auto it : hash) {
// If the number is 0
if (it.first == 0) {
// We take half since same number
count += it.second / 2;
if (it.first % 2 == 0)
hash[it.first] = 0;
else
hash[it.first] = 1;
}
else {
int first = it.first;
int second = k - it.first;
// Check for minimal occurrence
if (hash[first] < hash[second]) {
// Take the minimal
count += hash[first];
// Subtract the pairs used
hash[second] -= hash[first];
hash[first] = 0;
}
else if (hash[first] > hash[second]) {
// Take the minimal
count += hash[second];
// Subtract the pairs used
hash[first] -= hash[second];
hash[second] = 0;
}
else {
// Check if numbers are same
if (first == second) {
// If same then number of pairs will be half
count += it.second / 2;
// Check for remaining
if (it.first % 2 == 0)
hash[it.first] = 0;
else
hash[it.first] = 1;
}
else {
// Store the number of pairs
count += hash[first];
hash[first] = 0;
hash[second] = 0;
}
}
}
}
return count;
}
// Driver code
int main()
{
int a[] = { 1, 2, 2, 3, 2, 4, 10 };
int n = sizeof(a) / sizeof(a[0]);
int k = 2;
cout << findMaximumPairs(a, n, k);
return 0;
}
Java
// Java program to implement the above
// approach
import java.util.*;
class GFG
{
// Function to maximize the number of pairs
static int findMaximumPairs(int a[], int n, int k)
{
// Hash-table
HashMap<Integer,Integer> hash = new HashMap<Integer,Integer>();
for (int i = 0; i < n; i++)
if(hash.containsKey(a[i] % k)){
hash.put(a[i] % k, hash.get(a[i] % k)+1);
}
else{
hash.put(a[i] % k, 1);
}
int count = 0;
// Iterate for all numbers less than hash values
for (Map.Entry<Integer,Integer> it : hash.entrySet()){
// If the number is 0
if (it.getKey() == 0) {
// We take half since same number
count += it.getValue() / 2;
if (it.getKey() % 2 == 0)
hash.put(it.getKey(), 0);
else
hash.put(it.getKey(), 1);
}
else {
int first = it.getKey();
int second = k - it.getKey();
// Check for minimal occurrence
if (hash.get(first) < hash.get(second))
{
// Take the minimal
count += hash.get(first);
// Subtract the pairs used
hash.put(second, hash.get(second)-hash.get(first));
hash.put(first, 0);
}
else if (hash.get(first) > hash.get(second))
{
// Take the minimal
count += hash.get(second);
// Subtract the pairs used
hash.put(first, hash.get(first)-hash.get(second));
hash.put(second, 0);
}
else
{
// Check if numbers are same
if (first == second) {
// If same then number of pairs will be half
count += it.getValue() / 2;
// Check for remaining
if (it.getKey() % 2 == 0)
hash.put(it.getKey(), 0);
else
hash.put(it.getKey(), 1);
}
else {
// Store the number of pairs
count += hash.get(first);
hash.put(first, 0);
hash.put(second, 0);
}
}
}
}
return count;
}
// Driver code
public static void main(String[] args)
{
int a[] = { 1, 2, 2, 3, 2, 4, 10 };
int n = a.length;
int k = 2;
System.out.print(findMaximumPairs(a, n, k));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to implement
# the above approach
# Function to maximize the
# number of pairs
def findMaximumPairs(a, n, k) :
# Hash-table
hash = {};
for i in range(n) :
if a[i] % k not in hash :
hash[a[i] % k] = 0
hash[a[i] % k] += 1
count = 0;
# Iterate for all numbers less
# than hash values
for keys,values in hash.items() :
# If the number is 0
if (keys == 0) :
# We take half since same number
count += values // 2;
if (keys % 2 == 0) :
hash[keys] = 0;
else :
hash[keys] = 1;
else :
first = keys;
second = k -keys;
# Check for minimal occurrence
if (hash[first] < hash[second]) :
# Take the minimal
count += hash[first];
# Subtract the pairs used
hash[second] -= hash[first];
hash[first] = 0;
elif (hash[first] > hash[second]) :
# Take the minimal
count += hash[second];
# Subtract the pairs used
hash[first] -= hash[second];
hash[second] = 0;
else :
# Check if numbers are same
if (first == second) :
# If same then number of pairs
# will be half
count += values // 2;
# Check for remaining
if (keys % 2 == 0) :
hash[keys] = 0;
else :
hash[keys] = 1;
else :
# Store the number of pairs
count += hash[first];
hash[first] = 0;
hash[second] = 0;
return count;
# Driver code
if __name__ == "__main__" :
a = [ 1, 2, 2, 3, 2, 4, 10 ];
n = len(a)
k = 2;
print(findMaximumPairs(a, n, k));
# This code is contributed by Ryuga
Javascript
<script>
// Javascript program to implement the above
// approach
// Function to maximize the number of pairs
function findMaximumPairs(a, n, k) {
// Hash-table
let hash = new Map();
for (let i = 0; i < n; i++) {
if (hash.has(a[i] % k)) {
hash.set(a[i] % k, hash.get(a[i] % k) + 1)
} else {
hash.set(a[i] % k, 1)
}
}
let count = 0;
// Iterate for all numbers less than hash values
for (let it of hash) {
// If the number is 0
if (it[0] == 0) {
// We take half since same number
count += Math.floor(it[1] / 2);
if (it[0] % 2 == 0)
hash.set(it[0], 0);
else
hash.set(it[0], 1);
}
else {
let first = it[0];
let second = k - it[0];
// Check for minimal occurrence
if (hash.get(first) < hash.get(second)) {
// Take the minimal
count += hash.get(first);
// Subtract the pairs used
hash.set(second, hash.get(second) - hash.get(first));
hash.set(first, 0);
}
else if (hash.get(first) > hash.get(second)) {
// Take the minimal
count += hash.get(second);
// Subtract the pairs used
hash.set(first, hash.get(first) - hash.get(second));
hash.set(second, 0);
}
else {
// Check if numbers are same
if (first == second) {
// If same then number of pairs will be half
count += Math.floor(it[1] / 2);
// Check for remaining
if (it[0] % 2 == 0)
hash.set(it[0], 0);
else
hash.set(it[0], 1);
}
else {
// Store the number of pairs
count += hash.get(first);
hash.set(first, 0);
hash.set(second, 0);
}
}
}
}
return count;
}
// Driver code
let a = [1, 2, 2, 3, 2, 4, 10];
let n = a.length;
let k = 2;
document.write(findMaximumPairs(a, n, k));
// This code is contributed by _saurabh_jaiswal
</script>
Producción:
3
Complejidad de tiempo: O (N), ya que estamos usando un bucle para atravesar N veces. Donde N es el número de elementos de la array.
Espacio auxiliar: O(N), ya que estamos usando espacio extra para el mapa. Donde N es el número de elementos de la array.