Difficulty: Easy | Acceptance: 52.30% | Paid: No Topics: Array, Hash Table, Math, Counting, Number Theory
You are given a 0-indexed integer array nums. A pair of indices i, j is called beautiful if 0 <= i < j < nums.length and 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 numbers are coprime if their greatest common divisor (gcd) is equal to 1.
- Examples
- Constraints
- Brute Force
- Optimized Counting
Examples
Example 1
Input: nums = [2,5,1,4]
Output: 5
Explanation: There are 5 beautiful pairs:
- (0,1): first digit of 2 is 2, last digit of 5 is 5, gcd(2,5) = 1
- (0,2): first digit of 2 is 2, last digit of 1 is 1, gcd(2,1) = 1
- (1,2): first digit of 5 is 5, last digit of 1 is 1, gcd(5,1) = 1
- (1,3): first digit of 5 is 5, last digit of 4 is 4, gcd(5,4) = 1
- (2,3): first digit of 1 is 1, last digit of 4 is 4, gcd(1,4) = 1
Example 2
Input: nums = [11,21,12]
Output: 2
Explanation: There are 2 beautiful pairs:
- (0,1): first digit of 11 is 1, last digit of 21 is 1, gcd(1,1) = 1
- (0,2): first digit of 11 is 1, last digit of 12 is 2, gcd(1,2) = 1
Constraints
2 <= nums.length <= 100
1 <= nums[i] <= 9999
Brute Force
Intuition Check every possible pair (i, j) where i < j, extract the first digit of nums[i] and last digit of nums[j], then verify if they are coprime using gcd.
Steps
- Iterate through all pairs (i, j) with i < j
- For each pair, extract first digit of nums[i] by repeatedly dividing by 10
- Extract last digit of nums[j] using modulo 10
- Check if gcd of these two digits equals 1
- Count all such beautiful pairs
class Solution:
def countBeautifulPairs(self, nums: list[int]) -> int:
def first_digit(n: int) -> int:
while n >= 10:
n //= 10
return n
def last_digit(n: int) -> int:
return n % 10
def gcd(a: int, b: int) -> int:
while b:
a, b = b, a % b
return a
count = 0
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
if gcd(first_digit(nums[i]), last_digit(nums[j])) == 1:
count += 1
return countComplexity
- Time: O(n² × log(max(nums))) for extracting digits and computing gcd
- Space: O(1)
- Notes: Simple but inefficient for large arrays. Works within constraints since n ≤ 100.
Optimized Counting
Intuition Since there are only 10 possible digits (0-9), we can precompute coprime relationships and use a frequency array to count first digits seen so far, avoiding the nested loop.
Steps
- Precompute a 10×10 matrix marking which digit pairs are coprime
- Maintain a frequency array counting occurrences of each first digit
- For each number, get its last digit and sum up counts of first digits that are coprime with it
- Add the current number’s first digit to the frequency array
class Solution:
def countBeautifulPairs(self, nums: list[int]) -> int:
def first_digit(n: int) -> int:
while n >= 10:
n //= 10
return n
def last_digit(n: int) -> int:
return n % 10
def gcd(a: int, b: int) -> int:
while b:
a, b = b, a % b
return a
# Precompute coprime matrix for digits 0-9
coprime = [[False] * 10 for _ in range(10)]
for i in range(10):
for j in range(10):
if gcd(i, j) == 1:
coprime[i][j] = True
count = 0
first_digit_count = [0] * 10
for num in nums:
ld = last_digit(num)
# Count first digits seen so far that are coprime with ld
for fd in range(10):
if coprime[fd][ld]:
count += first_digit_count[fd]
# Add first digit of current number
fd = first_digit(num)
first_digit_count[fd] += 1
return countComplexity
- Time: O(n × 10) = O(n) for single pass with constant digit lookup
- Space: O(1) for the 10×10 coprime matrix and frequency array
- Notes: Optimal solution leveraging the small digit space (0-9). Much faster than brute force for larger arrays.