Count Pairs with Digit Sum Divisible by K
Given an array of N integers A and an integer K, find the number of pairs (i, j) such that 0 <= i < j < N and the sum of digits of A[i] plus the sum of digits of A[j] is divisible by K.
The sum of digits of a non-negative integer is the sum of its decimal digits. For example, the sum of digits of 123 is 1 + 2 + 3 = 6.
Input
The first line contains two integers N and K. The second line contains N integers A_1, A_2, ..., A_N.
Output
Print a single integer, the count of such pairs.
Constraints
1 <= N <= 200000 1 <= K <= 100 0 <= A_i <= 10^9
Example 1
5 3 1 2 3 4 5
4
Pairs: (1,2), (1,5), (2,4), (3,3), (4,5). Digit sums: 1,2,3,4,5. Remainders mod 3: 1,2,0,1,2. Pairs of remainders that sum to 0 mod 3 are (1,2) and (0,0). Pairs (A[i], A[j]) with i<j: (1,2) -> 1+2=3 (rem 0); (1,5) -> 1+5=6 (rem 0); (2,4) -> 2+4=6 (rem 0); (4,5) -> 4+5=9 (rem 0). Note that A[i] value
Example 2
4 2 10 20 30 40
2
Digit sums: 1, 2, 3, 4. Remainders mod 2: 1, 0, 1, 0. Pairs of remainders that sum to 0 mod 2 are (1,1) and (0,0). Pairs (A[i], A[j]) with i<j: (10,30) -> ds(10)+ds(30)=1+3=4 (rem 0); (20,40) -> ds(20)+ds(40)=2+4=6 (rem 0). The sample output is 2.
Hints
Similar problems
- Count Distinct Prefix SumsMedium
- Subarray Sum MultiplesMedium
- Count Pairs with Equal Digit SumMedium
- Subsegment Sum Divisible by KMedium
- String PartitionMedium
- Count Pairs with Equal Digit ProductMedium
More topics: Hash Map and Hashing problems, Prefix Sums problems, Math and Number Theory problems
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
5 3 1 2 3 4 5
4 2 10 20 30 40