Count Pairs of Cyclically Equivalent Integers
Company: Capital One
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
# Count Pairs of Cyclically Equivalent Integers
Two non-negative integers are **cyclically equivalent** when their standard decimal strings have the same length and one string can be obtained by moving zero or more leading characters to the end of the other.
Given a list `numbers`, count unordered index pairs `(i, j)` with `i < j` whose values are cyclically equivalent. Equal values count as cyclically equivalent, and duplicate occurrences are distinct list elements.
## Function Signature
```python
def count_cyclic_pairs(numbers: list[int]) -> int:
...
```
## Constraints
- `0 <= len(numbers) <= 200_000`
- `0 <= numbers[i] <= 1_000_000_000`
- Standard decimal notation has no leading zero, except that zero is represented as `"0"`.
- The answer may exceed 32-bit range.
## Examples
```text
Input: numbers = [123, 312, 231, 45]
Output: 3
```
```text
Input: numbers = [10, 1, 10, 100]
Output: 1
```
```text
Input: numbers = [7, 7, 7]
Output: 3
```
Quick Answer: Count unordered index pairs whose non-negative integers have decimal strings equivalent under cyclic rotation. The algorithm challenge emphasizes a precise equivalence relation, duplicate occurrences, string-length and leading-zero semantics, scalability to 200,000 values, and pair counts beyond 32-bit range.
Two non-negative integers are **cyclically equivalent** when their standard decimal strings have the same length and one string can be obtained by moving zero or more leading characters of the other to the end.
Given a list `numbers`, count the unordered index pairs `(i, j)` with `i < j` whose values are cyclically equivalent. Moving zero characters is allowed, so equal values are cyclically equivalent, and duplicate occurrences are distinct list elements.
The test is applied to the two decimal strings themselves. Equal length is required before any rotation is considered, and an intermediate rotation that happens to begin with `0` is still a valid rotation - it is never read back as a number.
## Function Signature
```python
def count_cyclic_pairs(numbers: list[int]) -> int:
...
```
## Examples
```text
Input: numbers = [123, 312, 231, 45]
Output: 3
```
`123`, `312` and `231` are rotations of one another, giving the pairs `(0, 1)`, `(0, 2)` and `(1, 2)`. `45` matches nothing.
```text
Input: numbers = [10, 1, 10, 100]
Output: 1
```
Only the two `10` entries match. `1` and `100` have different digit lengths, so the equal-length rule rules them out.
```text
Input: numbers = [7, 7, 7]
Output: 3
```
Zero moves make equal values cyclically equivalent, and the three duplicates are three distinct elements, so all three index pairs count.
```text
Input: numbers = [201, 102]
Output: 0
```
The strings reachable from `"201"` are `"201"`, `"012"` and `"120"`; those reachable from `"102"` are `"102"`, `"021"` and `"210"`. Neither is reachable from the other, so sharing a digit multiset is not enough.
## Output
Return a single integer: the number of qualifying index pairs. Every input has exactly one correct answer, so no ordering or tie-breaking rule is involved.
Constraints
- 0 <= len(numbers) <= 200_000
- 0 <= numbers[i] <= 1_000_000_000
- Standard decimal notation has no leading zero, except that zero is represented as "0"
- The answer may exceed 32-bit range (it reaches C(200000, 2) = 19,999,900,000 at the maximum list length)
Examples
Input: ([],)
Expected Output: 0
Explanation: empty list: no index pair exists
Input: ([5],)
Expected Output: 0
Explanation: singleton: no index pair exists
Hints
- Cyclic equivalence is an equivalence relation on the decimal strings, so instead of comparing every pair, give each value one representative of its rotation class and group by it.
- Every rotation of a string of length L appears as a length-L window of that string concatenated with itself.
- Once the values are grouped, the answer is decided by the group sizes alone - and that total can outgrow a signed 32-bit integer, so size the accumulator accordingly.