Count Digit-Reversal Equivalent Pairs
Company: Hudson River Trading
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Define `flipdigits(x)` as the integer produced by reversing the decimal digits of non-negative integer `x` and removing leading zeroes from the reversed result.
Examples:
```text
flipdigits(5070) = 705
flipdigits(800) = 8
flipdigits(123) = 321
```
Given an array `arr` of non-negative integers, count how many pairs `(i, j)` satisfy `i <= j` and:
```text
arr[i] + flipdigits(arr[j]) = arr[j] + flipdigits(arr[i])
```
Return the count as an integer.
Example 1:
```text
arr = [1, 20, 2, 11]
output = 7
```
Example 2:
```text
arr = [32, 332, 100]
output = 4
```
Constraints:
- `0 <= arr.length <= 100000`
- `0 <= arr[i] <= 10^9`
- Count pairs with `i <= j`, so each element pairs with itself.
Quick Answer: This Hudson River Trading coding question tests hash-based counting for pairs that become equivalent after a digit-reversal transform. It is useful for practicing canonicalization, duplicate accounting, and careful handling of numeric string edge cases.
For each non-negative integer x, flipdigits(x) reverses its decimal digits and removes leading zeroes. Count pairs (i, j) with i <= j such that arr[i] + flipdigits(arr[j]) = arr[j] + flipdigits(arr[i]).
Constraints
- 0 <= arr.length <= 100000
- 0 <= arr[i] <= 10^9
- Pairs include i == j.
Examples
Input: ([1, 20, 2, 11],)
Expected Output: 7
Input: ([32, 332, 100],)
Expected Output: 4
Hints
- Rearrange the equation.
- Values with the same x - flipdigits(x) form valid pairs.
- For a group of size c, there are c * (c + 1) / 2 pairs with i <= j.