-
Notifications
You must be signed in to change notification settings - Fork 9
/
K-Divisibility of an Array.py
49 lines (38 loc) · 1.3 KB
/
K-Divisibility of an Array.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
You are given an array A of size N.
You are also givena number K.
Let us define what K-Divisibility of an array means :
K-Divisibility of an array is the number of unordered pairs (i,j) such that Ai + Aj is divisible by K.
Your task is to find and print the K-Divisibility of the given array A.
INPUT
First line contains two integers, size of array N and the value K.
Second line contains N space separated integers, ith of which denotes Ai.
OUTPUT
Print one value, the K-Divisibility of the array.
Sample Input 0
6 5
1 2 3 4 5 6
Sample Output 0
3
def countKdivPairs(A, n, K):
# Create a frequency array to count
# occurrences of all remainders when
# divided by K
freq = [0 for i in range(K)]
# To store count of pairs.
ans = 0
# Traverse the array, compute the remainder
# and add k-remainder value hash count to ans
for i in range(n):
rem = A[i] % K
# Count number of ( A[i], (K - rem)%K ) pairs
ans += freq[(K - rem) % K]
# Increment count of remainder in hash map
freq[rem] += 1
return ans
# Driver code
if __name__ == '__main__':
n,K=map(int,input().split())
A = list(map(int,input().split()))
print(countKdivPairs(A, n, K))
# This code is contributed by
# Surendra_Gangwar, Yadvendra Naveen