2748. Number of Beautiful Pairs
Description
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 <= 100
1 <= nums[i] <= 9999
nums[i] % 10 != 0
Solutions
Solution 1: Counting
We can use an array $\textit{cnt}$ of length $10$ to record the count of the first digit of each number.
Iterate through the array $\textit{nums}$. For each number $x$, we enumerate each digit $y$ from $0$ to $9$. If $\textit{cnt}[y]$ is not $0$ and $\textit{gcd}(x \mod 10, y) = 1$, then the answer is incremented by $\textit{cnt}[y]$. Then, we increment the count of the first digit of $x$ by $1$.
After the iteration, return the answer.
The time complexity is $O(n \times (k + \log M))$, and the space complexity is $O(k + \log M)$. Here, $n$ is the length of the array $\textit{nums}$, while $k$ and $M$ respectively represent the number of distinct numbers and the maximum value in the array $\textit{nums}$.
1 2 3 4 5 6 7 8 9 10 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
|