In this guide, you will get 2748. Number of Beautiful Pairs LeetCode Solution with the best time and space complexity. The solution to Number of Beautiful Pairs problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
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.
2748. Number of Beautiful Pairs LeetCode Solution in C++
class Solution {
public:
int countBeautifulPairs(vector<int>& nums) {
int ans = 0;
for (int i = 0; i < nums.size(); ++i)
for (int j = i + 1; j < nums.size(); ++j)
if (__gcd(firstDigit(nums[i]), lastDigit(nums[j])) == 1)
++ans;
return ans;
}
private:
int firstDigit(int num) {
return to_string(num)[0] - '0';
}
int lastDigit(int num) {
return num % 10;
}
}; /* code provided by PROGIEZ */
2748. Number of Beautiful Pairs LeetCode Solution in Java
class Solution {
public int countBeautifulPairs(int[] nums) {
int ans = 0;
for (int i = 0; i < nums.length; ++i)
for (int j = i + 1; j < nums.length; ++j)
if (gcd(firstDigit(nums[i]), lastDigit(nums[j])) == 1)
++ans;
return ans;
}
private int firstDigit(int num) {
return Integer.parseInt(Integer.toString(num).substring(0, 1));
}
private int lastDigit(int num) {
return num % 10;
}
private int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
} // code provided by PROGIEZ
2748. Number of Beautiful Pairs LeetCode Solution in Python
class Solution:
def countBeautifulPairs(self, nums: list[int]) -> int:
def firstDigit(num: int) -> int:
return int(str(num)[0])
def lastDigit(num: int) -> int:
return num % 10
return sum(math.gcd(firstDigit(nums[i]), lastDigit(nums[j])) == 1
for i in range(len(nums))
for j in range(i + 1, len(nums))) # code by PROGIEZ
