Katkat
Back

Count Pairs of Cyclically Equivalent Integers

Capital OneSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

This problem tests your ability to normalize strings under cyclic rotation using hashing or canonical representation, combined with frequency counting to efficiently identify equivalent pairs.

Problem Statement

Given an array of non-negative integers nums, two integers are considered "cyclically equivalent" if their decimal string representations are rotations of each other. For example, "123" is equivalent to "231" and "312", but not "132".

Your task is to calculate the total number of unordered index pairs (i, j) such that i int:

Constraints

  • 1 <= len(nums) <= 200,000
  • 0 <= nums[i] <= 10^18
  • Return the total count as an integer (note that the result can exceed the 32-bit integer limit).

Examples

Example 1: Input: nums = [12, 21, 12] Output: 3 Explanation: The pairs are (index 0, 1), (0, 2), and (1, 2). All represent the same cyclic group.

Example 2: Input: nums = [10, 1] Output: 1 Explanation: "10" rotated is "01". Since the input is integer-based, we treat them as strings: "10" vs "01". Wait—if the problem treats them as decimal strings, "10" and "01" are distinct unless leading zeros are handled via string length. Note: If the integers are treated as strings of equal length, "10" and "01" are equivalent. For this problem, assume numbers are strings of the same length as their original representation (e.g., 5 is "5", 10 is "10"). If lengths differ, they cannot be equivalent.

Edge Cases

  • Single-digit numbers.
  • Numbers that are the same (e.g., 121 and 121).
  • Numbers that have different digit counts (they can never be equivalent).

Hints

Hint 1

To determine if two strings are cyclically equivalent, you can find the lexicographically smallest rotation of the string and use it as a canonical key.

Hint 2

Since numbers with different lengths cannot be equivalent, group the input numbers by their string length first.

Hint 3

Use a hash map to store the frequency of each canonical representation and compute the number of pairs using the formula n * (n - 1) / 2 for each group.

Follow-up questions

  • How would your approach change if leading zeros were not allowed, or if the integers were provided as strings of arbitrary length?
  • What is the time complexity of finding the canonical form for a string of length L, and how does this affect the overall complexity?
  • Can you solve this problem in O(N * L) time, where N is the number of integers and L is the average number of digits?