Cuente pares en una array cuya suma sea divisible por K

Dada una array A[] y un entero positivo K , la tarea es contar el número total de pares en la array cuya suma es divisible por K . 
Nota: Esta pregunta es una versión generalizada de esta 

Ejemplos: 

Input : A[] = {2, 2, 1, 7, 5, 3}, K = 4
Output : 5
Explanation : 
There are five pairs possible whose sum
is divisible by '4' i.e., (2, 2), 
(1, 7), (7, 5), (1, 3) and (5, 3)

Input : A[] = {5, 9, 36, 74, 52, 31, 42}, K = 3
Output : 7

Enfoque ingenuo : el enfoque más simple es iterar a través de cada par de la array pero usando dos bucles for anidados y contar aquellos pares cuya suma es divisible por ‘K’. La complejidad temporal de este enfoque es O(N ² ).

Enfoque eficiente : un enfoque eficiente es utilizar la técnica Hashing. Separaremos los elementos en cubos dependiendo de su (valor mod K). Cuando un número se divide por K, el resto puede ser 0, 1, 2, hasta (k-1). Así que tome una array para decir freq[] de tamaño K (inicializado con cero) y aumente el valor de freq[A[i]%K] para que podamos calcular la cantidad de valores que dan el resto j en la división con K.

// C++ Program to count pairs
// whose sum divisible by 'K'
#include <bits/stdc++.h>
using namespace std;
 
// Program to count pairs whose sum divisible
// by 'K'
int countKdivPairs(int A[], int n, int K)
{
    // Create a frequency array to count
    // occurrences of all remainders when
    // divided by K
    int freq[K] = { 0 };
 
    // Count occurrences of all remainders
    for (int i = 0; i < n; i++)
        ++freq[A[i] % K];
 
    // If both pairs are divisible by 'K'
    int sum = freq[0] * (freq[0] - 1) / 2;
 
    // count for all i and (k-i)
    // freq pairs
    for (int i = 1; i <= K / 2 && i != (K - i); i++)
        sum += freq[i] * freq[K - i];
    // If K is even
    if (K % 2 == 0)
        sum += (freq[K / 2] * (freq[K / 2] - 1) / 2);
    return sum;
}
 
// Driver code
int main()
{
 
    int A[] = { 2, 2, 1, 7, 5, 3 };
    int n = sizeof(A) / sizeof(A[0]);
    int K = 4;
    cout << countKdivPairs(A, n, K);
 
    return 0;
}

// Java program to count pairs
// whose sum divisible by 'K'
import java.util.*;
 
class Count {
    public static int countKdivPairs(int A[], int n, int K)
    {
        // Create a frequency array to count
        // occurrences of all remainders when
        // divided by K
        int freq[] = new int[K];
 
        // Count occurrences of all remainders
        for (int i = 0; i < n; i++)
            ++freq[A[i] % K];
 
        // If both pairs are divisible by 'K'
        int sum = freq[0] * (freq[0] - 1) / 2;
 
        // count for all i and (k-i)
        // freq pairs
        for (int i = 1; i <= K / 2 && i != (K - i); i++)
            sum += freq[i] * freq[K - i];
        // If K is even
        if (K % 2 == 0)
            sum += (freq[K / 2] * (freq[K / 2] - 1) / 2);
        return sum;
    }
    public static void main(String[] args)
    {
        int A[] = { 2, 2, 1, 7, 5, 3 };
        int n = 6;
        int K = 4;
        System.out.print(countKdivPairs(A, n, K));
    }
}

# Python3 code to count pairs whose
# sum is divisible by 'K'
 
# Function to count pairs whose
# sum is divisible by 'K'
def countKdivPairs(A, n, K):
     
    # Create a frequency array to count
    # occurrences of all remainders when
    # divided by K
    freq = [0] * K
     
    # Count occurrences of all remainders
    for i in range(n):
        freq[A[i] % K]+= 1
         
    # If both pairs are divisible by 'K'
    sum = freq[0] * (freq[0] - 1) / 2;
     
    # count for all i and (k-i)
    # freq pairs
    i = 1
    while(i <= K//2 and i != (K - i) ):
        sum += freq[i] * freq[K-i]
        i+= 1
 
    # If K is even
    if( K % 2 == 0 ):
        sum += (freq[K//2] * (freq[K//2]-1)/2);
     
    return int(sum)
 
# Driver code
A = [2, 2, 1, 7, 5, 3]
n = len(A)
K = 4
print(countKdivPairs(A, n, K))

// C# program to count pairs
// whose sum divisible by 'K'
using System;
 
class Count
{
    public static int countKdivPairs(int []A, int n, int K)
    {
        // Create a frequency array to count
        // occurrences of all remainders when
        // divided by K
        int []freq = new int[K];
 
        // Count occurrences of all remainders
        for (int i = 0; i < n; i++)
            ++freq[A[i] % K];
 
        // If both pairs are divisible by 'K'
        int sum = freq[0] * (freq[0] - 1) / 2;
 
        // count for all i and (k-i)
        // freq pairs
        for (int i = 1; i <= K / 2 && i != (K - i); i++)
            sum += freq[i] * freq[K - i];
             
        // If K is even
        if (K % 2 == 0)
            sum += (freq[K / 2] * (freq[K / 2] - 1) / 2);
        return sum;
    }
     
    // Driver code
    static public void Main ()
    {
        int []A = { 2, 2, 1, 7, 5, 3 };
        int n = 6;
        int K = 4;
        Console.WriteLine(countKdivPairs(A, n, K));
    }
}
 
// This code is contributed by akt_mit.

<?php
// PHP Program to count pairs
// whose sum divisible by 'K'
 
// Program to count pairs whose sum
// divisible by 'K'
function countKdivPairs($A, $n, $K)
{
     
    // Create a frequency array to count
    // occurrences of all remainders when
    // divided by K
    $freq = array_fill(0, $K, 0);
 
    // Count occurrences of all remainders
    for ($i = 0; $i < $n; $i++)
        ++$freq[$A[$i] % $K];
 
    // If both pairs are divisible by 'K'
    $sum = (int)($freq[0] * ($freq[0] - 1) / 2);
 
    // count for all i and (k-i)
    // freq pairs
    for ($i = 1; $i <= $K / 2 &&
                 $i != ($K - $i); $i++)
        $sum += $freq[$i] * $freq[$K - $i];
         
    // If K is even
    if ($K % 2 == 0)
        $sum += (int)($freq[(int)($K / 2)] *
                     ($freq[(int)($K / 2)] - 1) / 2);
    return $sum;
}
 
// Driver code
$A = array( 2, 2, 1, 7, 5, 3 );
$n = count($A);
$K = 4;
echo countKdivPairs($A, $n, $K);
 
// This code is contributed by mits
?>

<script>
    // Javascript program to count pairs whose sum divisible by 'K'
     
    function countKdivPairs(A, n, K)
    {
        // Create a frequency array to count
        // occurrences of all remainders when
        // divided by K
        let freq = new Array(K);
        freq.fill(0);
  
        // Count occurrences of all remainders
        for (let i = 0; i < n; i++)
            ++freq[A[i] % K];
  
        // If both pairs are divisible by 'K'
        let sum = freq[0] * parseInt((freq[0] - 1) / 2, 10);
  
        // count for all i and (k-i)
        // freq pairs
        for (let i = 1; i <= K / 2 && i != (K - i); i++)
            sum += freq[i] * freq[K - i];
              
        // If K is even
        if (K % 2 == 0)
            sum += parseInt(freq[parseInt(K / 2, 10)] * (freq[parseInt(K / 2, 10)] - 1) / 2, 10);
        return sum;
    }
     
    let A = [ 2, 2, 1, 7, 5, 3 ];
    let n = 6;
    let K = 4;
    document.write(countKdivPairs(A, n, K));
         
</script>

Producción : 

 5

Complejidad temporal: O(N) 
Espacio auxiliar: O(K), ya que se ha tomado K espacio extra.

https://www.youtube.com/watch?v=5UJvXcSUyT0