Count Pairs with Equal Digit Sum
MediumPractice library · +20 XPmathhashingarrays
Given an array of N positive integers, find the number of pairs (i, j) such that i < j and the sum of digits of A[i] is equal to the sum of digits of A[j].
Input
The first line contains an integer N. The second line contains N space-separated integers A_1, A_2, ..., A_N.
Output
Print a single integer: the total count of pairs (i, j) satisfying the conditions.
Constraints
1 <= N <= 200000 1 <= A_i <= 10^9
Time limit 1 s (native code; slower languages get more)Memory 256 MB15 hidden tests
Example 1
Input
5 12 3 45 6 111
Output
3
Digit sums: 1+2=3, 3, 4+5=9, 6, 1+1+1=3. Pairs with sum 3 are (12, 111). Count is 1.
Example 2
Input
6 1 10 100 1000 10000 100000
Output
15
All numbers have digit sum 1. There are 6 numbers, forming C(6,2) = 15 pairs.
Hints
Similar problems
- Count Pairs with Sum Divisible by KMedium
- Subarray Digit SumsMedium
- Count Pairs with Equal Digit ProductMedium
- Sum of Distinct ElementsMedium
- Two Sum Modulo KMedium
- Count Pairs with Digit Sum Divisible by KMedium
More topics: Arrays problems, Hash Map and Hashing 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()
Example 1 input
5 12 3 45 6 111
Example 2 input
6 1 10 100 1000 10000 100000