#2748

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Number of Beautiful Pairs

Count all index pairs in an array where the first digit of one number and last digit of another are coprime efficiently.

array hash table math counting number theory

Problem Statement

Given a 0-indexed array of integers nums, define a pair of indices (i, j) as beautiful if 0 <= i < j < nums.length and the first digit of nums[i] is coprime with the last digit of nums[j].

Return the total number of beautiful pairs in nums. Two integers are coprime if their greatest common divisor is 1.

Examples

Example 1

Input: nums = [2,5,1,4]

Output: 5

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

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

Solution Approach

Brute-force pair checking

Iterate over all possible pairs of indices (i, j) with nested loops, extract the first digit of nums[i] and last digit of nums[j], and check gcd(first, last) == 1. Increment count for each beautiful pair.

Use digit frequency hash

Store a hash table mapping last digits to their counts as you scan the array. For each first digit, check only relevant last digits in the hash to compute coprime relationships, reducing redundant gcd checks.

Optimize with precomputed coprime table

Precompute a 10x10 boolean table for digits 1-9 indicating if two digits are coprime. Then count beautiful pairs by looking up table entries for first digits against existing last digits in the hash.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time 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.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1: Counting

We can use an array $\textit{cnt}$ of length $10$ to record the count of the first digit of each number.

1

2

3

4

5

6

7

8

9

10

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

Continue Practicing

#3044 most frequent prime #3312 sorted gcd pair queries #2001 number of pairs of interchangeable rectangles