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

本文概述

C++
Java
Python3
C#
PHP

【算法题（对数组中的对进行计数，其和可被K整除）】给定数组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# 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 ?>

输出：