What is a beautiful pair in the Number of Beautiful Pairs problem?

A beautiful pair is a pair of indices (i, j) where i < j and the first digit of nums[i] is coprime with the last digit of nums[j].

Can I use a brute-force approach for this problem?

Yes, brute-force works for small arrays, but using a hash table for last digits and precomputed coprime table is faster.

How do I extract the first and last digits efficiently?

Last digit is nums[i] % 10. First digit can be found by dividing by 10 until the number is less than 10.

Why is the array scanning plus hash lookup pattern effective here?

It avoids repeated pairwise gcd calculations by counting last digits and referencing them for each first digit.

What constraints should I keep in mind for nums?

Array length is 2 to 100, nums[i] is 1 to 9999, and last digits are never zero, simplifying last digit extraction.

#2748

Easy

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

美丽下标对的数目

给你一个下标从 0 开始的整数数组 nums 。如果下标对 i 、 j 满足 0 ≤ i ，如果 nums[i] 的第一个数字和 nums[j] 的最后一个数字互质，则认为 nums[i] 和 nums[j] 是一组美丽下标对。返回 nums 中美丽下标对的总数目。对于两个整数…

数组哈希表数学计数数论

题目描述

给你一个下标从 0 开始的整数数组 nums 。如果下标对 i、j 满足 0 ≤ i < j < nums.length ，如果 nums[i] 的 第一个数字 和 nums[j] 的 最后一个数字 互质，则认为 nums[i] 和 nums[j] 是一组 美丽下标对 。

返回 nums 中 美丽下标对 的总数目。

对于两个整数 x 和 y ，如果不存在大于 1 的整数可以整除它们，则认为 x 和 y 互质。换而言之，如果 gcd(x, y) == 1 ，则认为 x 和 y 互质，其中 gcd(x, y) 是 x 和 y 的 最大公因数 。

示例 1：

输入：nums = [2,5,1,4]
输出：5
解释：nums 中共有 5 组美丽下标对：
i = 0 和 j = 1 ：nums[0] 的第一个数字是 2 ，nums[1] 的最后一个数字是 5 。2 和 5 互质，因此 gcd(2,5) == 1 。
i = 0 和 j = 2 ：nums[0] 的第一个数字是 2 ，nums[2] 的最后一个数字是 1 。2 和 1 互质，因此 gcd(2,1) == 1 。
i = 1 和 j = 2 ：nums[1] 的第一个数字是 5 ，nums[2] 的最后一个数字是 1 。5 和 1 互质，因此 gcd(5,1) == 1 。
i = 1 和 j = 3 ：nums[1] 的第一个数字是 5 ，nums[3] 的最后一个数字是 4 。5 和 4 互质，因此 gcd(5,4) == 1 。
i = 2 和 j = 3 ：nums[2] 的第一个数字是 1 ，nums[3] 的最后一个数字是 4 。1 和 4 互质，因此 gcd(1,4) == 1 。
因此，返回 5 。

示例 2：

输入：nums = [11,21,12]
输出：2
解释：共有 2 组美丽下标对：
i = 0 和 j = 1 ：nums[0] 的第一个数字是 1 ，nums[1] 的最后一个数字是 1 。gcd(1,1) == 1 。
i = 0 和 j = 2 ：nums[0] 的第一个数字是 1 ，nums[2] 的最后一个数字是 2 。gcd(1,2) == 1 。
因此，返回 2 。

提示：

2 <= nums.length <= 100
1 <= nums[i] <= 9999
nums[i] % 10 != 0

lightbulb

解题思路

方法一：计数

我们可以用一个长度为 $10$ 的数组 $\textit{cnt}$ 来记录每个数字的第一个数字出现的次数。

遍历数组 $\textit{nums}$ ，对于每个数字 $x$ ，我们枚举 $0$ 到 $9$ 的每个数字 $y$ ，如果 $\textit{cnt}[y]$ 不为 $0$ 且 $\textit{gcd}(x b\mod 10, y) = 1$ ，则答案加上 $\textit{cnt}[y]$ 。然后，我们将 $x$ 的第一个数字出现的次数加 $1$ 。

遍历结束后，返回答案即可。

时间复杂度 $O(n \times (k + \log M))$ ，空间复杂度 $O(k + \log M)$ 。其中 $n$ 为数组 $\textit{nums}$ 的长度，而 $k$ 和 $M$ 分别表示数组 $\textit{nums}$ 中的数字的种类以及最大值。

1

2

3

4

5

6

7

8

9

10

11

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

speed

复杂度分析

指标	值
时间	complexity ranges from O(n^2) for naive pair checking to O(n) if using hash table with precomputed coprime relationships. Space complexity is O(10) for the digit frequency hash and coprime table.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Expecting you to notice nums.length is small and brute-force is feasible but can be optimized.
question_mark
Looking for awareness of coprime checking and avoiding repeated gcd calculations.
question_mark
Interested in using array scanning combined with hash lookup to efficiently count pairs.

warning

常见陷阱

外企场景

error
Forgetting that only the first digit of nums[i] and last digit of nums[j] matter.
error
Checking gcd for all pairs without using a hash leads to unnecessary repeated calculations.
error
Mistakenly including pairs where i >= j or last digits are zero.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Count beautiful pairs where first and last digits are multiples instead of coprime.
arrow_right_alt
Consider arrays with zeros and handle last digit extraction carefully.
arrow_right_alt
Extend to larger numbers or larger digit ranges requiring different hashing strategies.

help

常见问题

外企场景

继续练习

#3044 出现频率最高的质数 #3312 查询排序后的最大公约数 #2001 可互换矩形的组数