A ground-control team monitors n satellites, each continuously broadcasting a numeric beacon ID: a positive integer with no leading zeros. A rare firmware glitch can swap two digits within a single beacon's transmitted ID before it reaches the ground. Two satellites are said to have a colliding signal if their broadcast IDs are already identical, or if swapping exactly two digit positions within just ONE of the two IDs (leaving the other ID completely untouched) would make the two IDs identical.
Count the number of pairs of satellites (i, j) with i < j whose beacon IDs collide.
n.n space-separated integers, the beacon IDs nums[1..n].Print a single integer: the number of colliding pairs.
Example 1
Input
3 111 113 131
Expected
1
Explanation
111 and 113 differ only at the last digit (a single position), which no one swap can fix. 111 and 131 likewise differ at only one position. But 113 and 131 differ at exactly two positions (the last two digits), and those two digits are transposed versions of each other — swapping the last two digits of 113 gives 131. So there is exactly 1 colliding pair.
Example 2
Input
4 54 45 54 540
Expected
3
Explanation
540 has 3 digits while the others have 2, so it can never collide with any of them. Among 54 (index 1), 45 (index 2), and 54 (index 3): 54 and 45 differ at both digits, which are transposed, so they collide; the two 54's are identical, so they collide; and 45 collides with the second 54 the same way as the first. That gives 3 colliding pairs in total.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →