Count Pairs with Equal Digit Product
Given N integers, count the number of pairs (i, j) such that 0 <= i < j < N and the product of the digits of the i-th number is equal to the product of the digits of the j-th number. The product of digits of a single-digit number is the number itself. If any digit is 0, the product of digits is 0.
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 such pairs.
Constraints
1 <= N <= 200000 0 <= a_i <= 10^9
Example 1
5 12 21 34 43 13
2
Digit products: 1*2=2, 2*1=2, 3*4=12, 4*3=12, 1*3=3. Pairs with product 2: (12, 21). Pairs with product 12: (34, 43). Total pairs: 2.
Example 2
4 10 20 3 5
1
Digit products: 0, 0, 3, 5. Pairs with product 0: (10, 20). Total pairs: 1.
Hints
Similar problems
- Two Sum Modulo KMedium
- Count Pairs with Digit Sum Divisible by KMedium
- Count Pairs with Equal Digit SumMedium
- Count Pairs with Sum Divisible by KMedium
- Divisible by Last DigitMedium
- Count Distinct Prefix SumsMedium
More topics: 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()
5 12 21 34 43 13
4 10 20 3 5