You are given a 0-indexed integer array nums. A pair of indices i, j where 0 <= i < j < nums.length is called beautiful if the first digit of nums[i] and the last digit of nums[j] are coprime.
Return the total number of beautiful pairs in nums.
Two integers x and y are coprime if there is no integer greater than 1 that divides both of them. In other words, x and y are coprime if gcd(x, y) == 1, where gcd(x, y) is the greatest common divisor of x and y.
Example 1:
Input: nums = [2,5,1,4] Output: 5 Explanation: There are 5 beautiful pairs in nums: When i = 0 and j = 1: the first digit of nums[0] is 2, and the last digit of nums[1] is 5. We can confirm that 2 and 5 are coprime, since gcd(2,5) == 1. When i = 0 and j = 2: the first digit of nums[0] is 2, and the last digit of nums[2] is 1. Indeed, gcd(2,1) == 1. When i = 1 and j = 2: the first digit of nums[1] is 5, and the last digit of nums[2] is 1. Indeed, gcd(5,1) == 1. When i = 1 and j = 3: the first digit of nums[1] is 5, and the last digit of nums[3] is 4. Indeed, gcd(5,4) == 1. When i = 2 and j = 3: the first digit of nums[2] is 1, and the last digit of nums[3] is 4. Indeed, gcd(1,4) == 1. Thus, we return 5.
Example 2:
Input: nums = [11,21,12] Output: 2 Explanation: There are 2 beautiful pairs: When i = 0 and j = 1: the first digit of nums[0] is 1, and the last digit of nums[1] is 1. Indeed, gcd(1,1) == 1. When i = 0 and j = 2: the first digit of nums[0] is 1, and the last digit of nums[2] is 2. Indeed, gcd(1,2) == 1. Thus, we return 2.
Constraints:
2 <= nums.length <= 1001 <= nums[i] <= 9999nums[i] % 10 != 0The goal of #2748 Number of Beautiful Pairs is to count pairs of indices (i, j) where i < j and the GCD of the first digit of nums[i] and the last digit of nums[j] equals 1. A direct approach is to check every pair, extract the required digits, compute gcd(a, b), and count valid pairs. While simple, this brute-force method runs in O(n²) time.
A more efficient idea uses digit counting. Since the first digit of any number ranges from 1 to 9, you can maintain frequency counts of previously seen first digits while scanning the array. For each element, compute its last digit and check which stored first digits form a coprime pair using gcd. Because there are only nine possible digits, this check is constant-sized. This reduces the complexity to roughly O(n) with a small constant factor and O(1) extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Brute Force Pair Checking | O(n^2) | O(1) |
| Digit Counting with GCD Checks | O(n) | O(1) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
Since nums.length is small, you can find all pairs of indices and check if each pair is beautiful.
Use integer to string conversion to get the first and last digit of each number.
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
A pair is considered beautiful when the greatest common divisor of the first digit of one number and the last digit of another equals 1. Using the GCD operation helps determine whether the two digits are coprime.
Yes, problems like this are common in coding interviews because they combine arrays, number theory, and counting techniques. Interviewers often use such questions to test optimization from brute force to more efficient counting strategies.
A small frequency array or hash map for digits 1 through 9 works best. It stores how many times each first digit has appeared so far, allowing quick checks against the current element's last digit.
The optimal approach uses counting with number theory. While iterating through the array, track frequencies of the first digits of previous numbers and compare them with the current number's last digit using a GCD check. Since digits range only from 1 to 9, the operation stays constant per element.