Digit Sum Pairs

The first line of input contains an integer N, the number of elements in the array.

The second line contains N space-separated integers, representing the elements of the array.

The output should be a single integer:
- The total number of unique pairs, if any exist.
- -1 if no valid pairs can be formed.

The input array contains unique positive integers.
A pair (a, b) is the same as (b, a). For example, if you count the pair (23, 50), you should not also count (50, 23).
The numbers within a pair must be different.

Sample Input 1:

5
12 21 34 43 50

Sample Output 1:

2

Explanation for Sample 1:

1. Calculate the digit sum for each number:
12 -> 1 + 2 = 3
21 -> 2 + 1 = 3
34 -> 3 + 4 = 7
43 -> 4 + 3 = 7
50 -> 5 + 0 = 5

2. Group numbers by their digit sum:
Sum 3: {12, 21}
Sum 7: {34, 43}
Sum 5: {50}

3. Form pairs from the groups:
From the "Sum 3" group, we can form the pair (12, 21). This is 1 pair.
From the "Sum 7" group, we can form the pair (34, 43). This is 1 pair.
The "Sum 5" group only has one number, so no pairs can be formed.

=> Total unique pairs = 1 + 1 = 2.

Sample Input 2:

4

1 2 3 4

Sample Output 2:

-1

Explanation for Sample 2:

The digit sums are 1, 2, 3, and 4. Since all digit sums are unique, no pairs of numbers share the same digit sum. Therefore, the output is -1.

Expected Time Complexity:

The expected time complexity is O(N * log(M)), where N is the number of elements in the array and M is the largest number in the array (the log factor comes from calculating the digit sum).

Constraints:

1 <= N <= 10^5
1 <= arr[i] <= 10^9

Time limit: 1 secx