Katkat
Back

Count Digit-Reversal Equivalent Pairs

Hudson River TradingSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

Count pairs of indices in an integer array whose values share the same canonical digit-reversal form.

Problem Statement

You are given an array of non-negative integers nums.

Two integers $a$ and $b$ are considered digit-reversal equivalent if they can both be reduced to the same integer through zero or more digit-reversal operations.

In a single digit-reversal operation on an integer $x$:

  1. The digits of $x$ (in base 10) are reversed.
  2. Any leading zeros resulting from the reversal are stripped, yielding standard integer representation.

For example, applying the operation to 1200 yields 21, and applying it again yields 12. Both 1200 and 21 can reach 12 (and 21), so 1200, 12, and 21 are all mutually equivalent.

Return the total number of pairs of indices (i, j) such that `0 int: pass


## Constraints

- `1 <= len(nums) <= 10^5`
- `0 <= nums[i] <= 10^9`

## Examples

### Example 1

```text
Input: nums = [12, 21, 120, 34, 4300]
Output: 4

Explanation:

  • 12, 21, and 120 are all equivalent to each other. They form 3 pairs: (0, 1), (0, 2), and (1, 2).
  • 34 and 4300 are equivalent to each other (both can reach 34 and 43). They form 1 pair: (3, 4).
  • Total equivalent pairs = 3 + 1 = 4.

Example 2

Input: nums = [0, 0, 7, 70, 700]
Output: 4

Explanation:

  • nums[0] = 0 and nums[1] = 0 are equivalent (pair (0, 1)).
  • 7, 70, and 700 are all equivalent to each other (3 pairs: (2, 3), (2, 4), (3, 4)).
  • Total equivalent pairs = 1 + 3 = 4.

Hints

Hint 1

Notice that stripping trailing zeros from any positive integer produces a core value that alternates between itself and its reversed digits upon repeated reversal.

Hint 2

Define a canonical representation for each number: for x > 0, strip all trailing zeros to get s, reverse s to get r, and take min(s, r) as the representative.

Hint 3

Handle 0 as a special case, map each element in nums to its canonical key, and use a frequency hash map to compute n * (n - 1) // 2 pairs for each group.

Follow-up questions

  • How would your approach change if the base were variable (e.g., base b where 2 <= b <= 36) rather than base 10?
  • If the array elements could be up to 10^100 (big integers given as strings), how would you optimize the memory and string hashing?
  • What if the equivalence relation only allowed at most one reversal operation rather than arbitrary sequences of reversals?