🔗 🟢 2748. Number of Beautiful Pairs 1301

tags: `Weekly Contest 351` `數學(Math)` `最大公因數(GCD)` `暴力法(Brute Force)` `計數(Counting)` `雜湊表(Hash Table)`

題意

給定一個下標從 $0$ 開始的整數陣列 $nums$ 。若存在一對索引 $(i, j)$ ，滿足 $0 \leq i < j < \text{nums.length}$ ，且 $\text{nums}[i]$ 的第一位數字與 $\text{nums}[j]$ 的最後一位數字互質的話，就稱這對索引為 美麗對(beautiful pairs) 。

返回 $nums$ 中美麗對的總數。

對於兩個整數 $x$ 和 $y$ ，若沒有大於 $1$ 的整數能同時整除它們，則稱它們為互質。換句話說，若 $x$ 和 $y$ 的最大公因數為 $1$ ，則它們互質。

約束條件

$2 \leq n = \text{nums.length} \leq 100$
$1 \leq \text{nums}[i] \leq 9999$
$\text{nums}[i] \mod 10 \neq 0$

思路

gcd 函數是計算兩個整數的最大公因數，可以使用遞迴或迭代的方式來實現，這裡使用遞迴的方式，定義 gcd 函數如下：

若 $b = 0$ ，則 $\gcd(a, b) = a$ ，
否則 $\gcd(a, b) = \gcd(b, a \mod b)$ 。

由於需要計算一個數字的第一個數字和最後一個數字，可以使用除法和取餘數的方式來實現：

取出一個數字 $x$ 的第一個數字，可以將 $x$ 除以 $10$ 直到 $x$ 小於 $10$ 為止，最後的 $x$ 即為第一個數字。
取出一個數字 $x$ 的最後一個數字，可以將 $x \bmod 10$ 即可。

方法一：暴力法(Brute Force)

由於 $n \leq 100$ ，因此可以使用暴力法來解決這個問題。使用兩個迴圈來列舉所有可能的索引組合 $(i, j)$ ，然後檢查是否這對索引構成一個美麗對。具體來說，我們對 $\text{nums}[i]$ 的第一位數字 $y$ 和 $\text{nums}[j]$ 的最後一位數字 $x$ 做最大公因數的檢查，若等於 $1$ 則代表兩個數字互質，算作一個美麗對，將答案 $ans$ 加 1。

複雜度分析

時間複雜度： $\mathcal{O}(n^2 \log M)$ $O (n^{2} lo g M)$ ，其中 $n$ $n$ 是陣列 $nums$ $n u m s$ 的長度， $M$ $M$ 是陣列 $nums$ $n u m s$ 中的最大值。
- 遍歷所有可能的 $(i, j)$ 對需要 $\mathcal{O}(n^2)$ 的時間。
- 計算 $\text{nums}[i]$ 的第一位數字 $y$ 需要 $\mathcal{O}(\log M)$ 的時間。
- 由於 $x, y < 10$ ，因此計算最大公因數的時間可以視為常數時間。
空間複雜度： $\mathcal{O}(1)$ 。

class Solution:
    def countBeautifulPairs(self, nums: List[int]) -> int:
        n = len(nums)
        ans = 0
        for i in range(n):
            for j in range(i+1, n):
                y = nums[i]
                while y >= 10:
                    y //= 10
                x = nums[j] % 10
                if gcd(y, x) == 1:
                    ans += 1
        return ans

class Solution {
public:
    int countBeautifulPairs(vector<int>& nums) {
        int n = nums.size(), ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                int y = nums[i];
                while (y >= 10) {
                    y /= 10;
                }
                int x = nums[j] % 10;
                if (gcd(y, x) == 1) { // or __gcd
                    ans++;
                }
            }
        }
        return ans;
    }
    int gcd(int a, int b) {
        return b ? gcd(b, a % b) : a;
    }
};

方法二：計數(Counting)

從方法一中可以發現，對於 $\text{nums}[j]$ 的最後一位數字 $x$ ，只需要考慮前面有多少數字的第一個數字 $y$ 與 $x$ 互質即可。

因此可以使用一個長度為 $10$ 的計數陣列 $cnt$ 來記錄每個數字的出現次數。對於每一個數字 $x$ ，我們找出它的最後一位數字 $x \% 10$ ，然後和 $1$ 到 $9$ 之間的數字進行最大公因數檢查，若為 $1$ 則意味兩數互質，可以構成美麗對，將 $cnt$ 中對應的值加到答案 $ans$ 上。

最後，我們更新 $cnt$ 陣列，將 $x$ 的第一個數字的計數增加 1。

複雜度分析

時間複雜度： $\mathcal{O}(n)$ ，其中 $n$ 是陣列 $nums$ 的長度。
空間複雜度： $\mathcal{O}(10) = \mathcal{O}(1)$ 。

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

class Solution {
public:
    int countBeautifulPairs(vector<int>& nums) {
        int n = nums.size(), ans = 0;
        vector<int> cnt(10);
        for (int x : nums) {
            for (int y = 1; y < 10; y++) {
                if (gcd(y, x % 10) == 1) { // or __gcd
                    ans += cnt[y];
                }
            }
            while (x >= 10) {
                x /= 10;
            }
            cnt[x]++;
        }
        return ans;
        
    }
    int gcd(int a, int b) {
        return b ? gcd(b, a % b) : a;
    }
};