Count Pairs of Cyclically Equivalent Integers

Question

The question asks the candidate to count pairs of integers that are cyclically equivalent within a given list.

Codemia · Accepted Answer

To solve the problem of counting pairs of cyclically equivalent integers, we first need to define what cyclic equivalence means. Two integers are cyclically equivalent if one can be obtained from the other by rotating its digits. For example, the integers 123 and 231 are cyclically equivalent. The goal is to count how many such pairs exist in the provided list.

1. **Normalization**: For each integer, generate its normalized form by rotating its digits to find the smallest lexicographical representation. This will help in grouping cyclically equivalent integers together.
2. **Counting**: Use a dictionary to count occurrences of each normalized form. For each unique normalized form with a count of `n`, the number of pairs can be calculated using the combination formula `C(n, 2) = n * (n - 1) / 2`.
3. **Summation**: Sum the counts of pairs for all unique normalized forms to get the final result.

The time complexity of this approach is O(m * n), where `m` is the number of integers and `n` is the average number of digits in these integers. The space complexity is O(k), where `k` is the number of unique normalized forms stored in the dictionary.

```python
def count_cyclic_pairs(nums):
    from collections import defaultdict
    def normalize(num):
        s = str(num)
        return min(s[i:] + s[:i] for i in range(len(s)))

count_map = defaultdict(int)
    for num in nums:
        norm = normalize(num)
        count_map[norm] += 1

total_pairs = 0
    for count in count_map.values():
        if count > 1:
            total_pairs += count * (count - 1) // 2

return total_pairs
```

It is important to consider edge cases, such as when the input list is empty or contains only one integer. In these cases, the output should be zero since no pairs can be formed. Additionally, handling leading zeros in integers should be addressed during normalization.

Count Pairs of Cyclically Equivalent Integers

Capital One

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

Capital One Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string