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.
This approach involves examining each pair (i, j) where 0 <= i < j < nums.length. For each pair, we extract the first digit of nums[i] and the last digit of nums[j], then check if these two digits are coprime.
To extract the first digit of a number, we repeatedly divide the number by 10 until it's less than 10. For the last digit, we take the modulo 10 of the number. Two numbers are coprime if their greatest common divisor (GCD) is 1.
The C solution defines a helper function gcd() to calculate the greatest common divisor of two integers. Another helper function firstDigit() is used to extract the first digit of a number. The main function calculates the total number of beautiful pairs by iterating over all pairs of indices and using the helper functions to check the condition for being coprime.
Time Complexity: O(n^2), where n is the length of the input array, because we check each pair of elements once.
Space Complexity: O(1) as we use a constant amount of extra space.
This approach preprocesses both the first digits and last digits of all numbers beforehand, saving this information in separate arrays. We then iterate over pairs to determine the total number of beautiful pairs. By preprocessing, we avoid recomputing the first and last digits multiple times.
The optimized C solution preprocesses the input array to create arrays for first and last digits. This avoids repeated calculations during the main pair-checking loop, making the code more efficient by performing these common calculations upfront.
Time Complexity: O(n^2) — preprocessing takes O(n) and checking takes O(n^2).
Space Complexity: O(n) — additional space for first and last digit arrays.
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: Space Complexity: |
| Optimized Approach with Preprocessing | Time Complexity: Space Complexity: |
| 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 |
6466. Number of Beautiful Pairs | Leetcode | Weekly Contest 351 | Solution Code In Comment. • Optimization • 1,067 views views
Watch 5 more video solutions →Practice Number of Beautiful Pairs with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor