LeetCode 2748. Number of Beautiful Pairs Solution in Java, C++, Python & More | Explanation + Code

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 cnt of length 10 to record the count of the first digit of each number.

Iterate through the array nums. For each number x, we enumerate each digit y from 0 to 9. If cnt[y] is not 0 and gcd(x \mod 10, y) = 1, then the answer is incremented by 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 × (k + log M)), and the space complexity is O(k + log M). Here, n is the length of the array nums, while k and M respectively represent the number of distinct numbers and the maximum value in the array nums.

PythonJavaC++GoTypeScript

class Solution: def countBeautifulPairs(self, nums: List[int]) -> int: cnt = [0] * 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)[0])] += 1 return ans(code-box)

class Solution { public int countBeautifulPairs(int[] nums) { int[] cnt = new int[10]; 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); } }(code-box)

class Solution { public: int countBeautifulPairs(vector<int>& nums) { int cnt[10]{}; 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; } };(code-box)

func countBeautifulPairs(nums []int) (ans int) { cnt := [10]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) }(code-box)

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); }(code-box)