How do you solve Number of Beautiful Pairs on LeetCode?

Number of Beautiful Pairs (LeetCode #2748) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n + k²) time complexity and O(k) space complexity. Key insight: Understanding coprimality and how to efficiently check it using gcd.

What is the brute force solution for Number of Beautiful Pairs?

The brute force approach for Number of Beautiful Pairs is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach checks every possible pair of indices in the array. For each pair, it extracts the first digit of the first number and the last digit of the second number, then checks if they are coprime. The optimal Optimal Solution approach improves this to O(n + k²).

What algorithm or data structure is used to solve Number of Beautiful Pairs?

Number of Beautiful Pairs uses the following concepts: Array, Hash Table, Math, Counting, Number Theory. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Number of Beautiful Pairs?

Always clarify the constraints of the problem before jumping into coding. Think about edge cases, such as arrays with repeated digits. Discuss your thought process with the interviewer to showcase your understanding.

What are common mistakes when solving Number of Beautiful Pairs?

Forgetting to check the condition 0 <= i < j. Not using gcd correctly or misunderstanding coprimality.

#2748

Number of Beautiful Pairs

Easy

ArrayHash TableMathCountingNumber TheoryHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n + k²)
Space	O(1)	O(k)

💡

Intuition

Time O(n + k²)Space O(k)

We can optimize the solution by precomputing the first and last digits for all numbers and then using a frequency array to count occurrences. This allows us to quickly check coprimality without nested loops.

⚙️

Algorithm

5 steps

1Step 1: Create an array to count occurrences of first digits (1-9) and last digits (0-9).
2Step 2: Iterate through the nums array and fill the frequency arrays for first and last digits.
3Step 3: For each first digit, check against all last digits using the gcd function.
4Step 4: Multiply the counts of coprime pairs and accumulate the result.
5Step 5: Return the total count of beautiful pairs.

solution.py16 lines

1from math import gcd
2
3def countBeautifulPairs(nums):
4    first_count = [0] * 10
5    last_count = [0] * 10
6    for num in nums:
7        first_digit = int(str(num)[0])
8        last_digit = num % 10
9        first_count[first_digit] += 1
10        last_count[last_digit] += 1
11    count = 0
12    for i in range(1, 10):
13        for j in range(10):
14            if gcd(i, j) == 1:
15                count += first_count[i] * last_count[j]
16    return count

ℹ

Complexity note: The time complexity is O(n + k²) where n is the number of elements in nums and k is the number of unique digits (which is constant, 10). The space complexity is O(k) due to the frequency arrays.

1Understanding coprimality and how to efficiently check it using gcd.
2Recognizing patterns in the problem to optimize the solution.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.