算法题：对数组中的对进行计数，其和可被K整除

本文概述

• C++
• Java
• Python3
• C#
• PHP

给定数组A[]和正整数K，任务是计算数组中总和能被K整除的对的总数。

例子：

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

简单的方法：最简单的方法是遍历数组的每一对, 但使用两个嵌套的for循环并计算总和可被" K"整除的那些对。这种方法的时间复杂度是O(N2)。

高效方法：一种有效的方法是使用哈希技术。我们将根据元素(值mod K)将其分为多个存储桶。当数字除以K时, 余数可以是0、1、2, 最高为(k-1)。所以拿一个数组说频率[]大小为K(用零初始化), 并增加freq [A [i]％K]的值, 以便我们可以计算除以k的余数j的值的数量。

C++

//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

//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

# 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#

//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
//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
?>

输出：

5

时间复杂度：O(n)

辅助空间：O(1)

---