Watch 6 video solutions for Number of Beautiful Pairs, a easy level problem involving Array, Hash Table, Math. This walkthrough by Optimization has 1,067 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 != 0Problem Overview: You receive an array of integers. A pair (i, j) is considered beautiful when i < j and the first digit of nums[i] is coprime with the last digit of nums[j]. The task is to count how many such pairs exist.
Approach 1: Brute Force Pair Checking (O(n²) time, O(1) space)
The direct method checks every pair of indices (i, j) where i < j. Extract the first digit of nums[i] by repeatedly dividing by 10 until one digit remains, and compute the last digit of nums[j] using num % 10. For each pair, calculate gcd(firstDigit, lastDigit). If the result equals 1, the pair is beautiful. This approach uses simple iteration over the array and a standard GCD computation from number theory. It is easy to implement but inefficient for large arrays because it evaluates every possible pair.
Approach 2: Optimized Counting with Digit Frequency (O(n) time, O(1) space)
The key observation: only digits 1–9 can appear as the first digit, and last digits range from 0–9. Instead of comparing every pair, maintain a frequency count of the first digits seen so far while scanning the array from left to right. For each element nums[j], compute its last digit. Then check which previously seen first digits are coprime with this last digit. Add the corresponding frequencies to the answer. Finally, extract the first digit of nums[j] and update the frequency table.
This turns pair comparison into a small constant loop over digits 1–9. GCD checks are cheap, and you only store a fixed-size frequency array, which acts like a lightweight hash table. The algorithm effectively converts pair enumeration into a counting problem using ideas from counting. Time complexity becomes linear in the size of the input because each number is processed once.
Recommended for interviews: Start by explaining the brute force solution to show you understand the pair condition and how digits are extracted. Then move to the optimized counting approach. Interviewers expect the linear-time method because it recognizes the limited digit range and replaces pair iteration with frequency aggregation.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Checking | O(n²) | O(1) | Small input sizes or when first learning the problem |
| Digit Frequency Counting (Optimized) | O(n) | O(1) | Preferred solution for interviews and large arrays |