# 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 is 2, and the last digit of nums 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 is 2, and the last digit of nums is 1. Indeed, gcd(2,1) == 1.
When i = 1 and j = 2: the first digit of nums is 5, and the last digit of nums is 1. Indeed, gcd(5,1) == 1.
When i = 1 and j = 3: the first digit of nums is 5, and the last digit of nums is 4. Indeed, gcd(5,4) == 1.
When i = 2 and j = 3: the first digit of nums is 1, and the last digit of nums 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 is 1, and the last digit of nums is 1. Indeed, gcd(1,1) == 1.
When i = 0 and j = 2: the first digit of nums is 1, and the last digit of nums 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

• class Solution {
public int countBeautifulPairs(int[] nums) {
int[] cnt = new int;
int ans = 0;
for (int x : nums) {
for (int y = 0; y < 10; ++y) {
if (cnt[y] > 0 && gcd(x % 10, y) == 1) {
ans += cnt[y];
}
}
while (x > 9) {
x /= 10;
}
++cnt[x];
}
return ans;
}

private int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
}

• class Solution {
public:
int countBeautifulPairs(vector<int>& nums) {
int cnt{};
int ans = 0;
for (int x : nums) {
for (int y = 0; y < 10; ++y) {
if (cnt[y] && gcd(x % 10, y) == 1) {
ans += cnt[y];
}
}
while (x > 9) {
x /= 10;
}
++cnt[x];
}
return ans;
}
};

• class Solution:
def countBeautifulPairs(self, nums: List[int]) -> int:
cnt =  * 10
ans = 0
for x in nums:
for y in range(10):
if cnt[y] and gcd(x % 10, y) == 1:
ans += cnt[y]
cnt[int(str(x))] += 1
return ans


• func countBeautifulPairs(nums []int) (ans int) {
cnt := int{}
for _, x := range nums {
for y := 0; y < 10; y++ {
if cnt[y] > 0 && gcd(x%10, y) == 1 {
ans += cnt[y]
}
}
for x > 9 {
x /= 10
}
cnt[x]++
}
return
}

func gcd(a, b int) int {
if b == 0 {
return a
}
return gcd(b, a%b)
}

• function countBeautifulPairs(nums: number[]): number {
const cnt: number[] = Array(10).fill(0);
let ans = 0;
for (let x of nums) {
for (let y = 0; y < 10; ++y) {
if (cnt[y] > 0 && gcd(x % 10, y) === 1) {
ans += cnt[y];
}
}
while (x > 9) {
x = Math.floor(x / 10);
}
++cnt[x];
}
return ans;
}

function gcd(a: number, b: number): number {
if (b === 0) {
return a;
}
return gcd(b, a % b);
}