Problem Description

You are given a 0-indexed integer array nums. Your task is to count the number of "beautiful pairs" in this array.

A pair of indices (i, j) where 0 <= i < j < nums.length is considered beautiful if:

• The first digit of nums[i] and the last digit of nums[j] are coprime

Two integers x and y are coprime if their greatest common divisor (GCD) equals 1. In other words, they share no common divisors other than 1.

For example:

• If nums[i] = 234, the first digit is 2
• If nums[j] = 567, the last digit is 7
• Since gcd(2, 7) = 1, this would be a beautiful pair

The problem asks you to return the total count of all beautiful pairs in the array.

Key Points:

• You need to check pairs where i < j (earlier index paired with later index)
• Extract the first digit of nums[i] and last digit of nums[j]
• Check if these two digits are coprime (their GCD is 1)
• Count all such valid pairs

Intuition

The naive approach would be to check every pair (i, j) where i < j, extract the first digit of nums[i] and last digit of nums[j], then check if they're coprime. This would take O(n²) time.

However, we can optimize this by observing a key insight: the first digit of any number can only be one of 9 values (1-9), and the last digit can only be one of 10 values (0-9). This limited range allows us to use counting.

The clever idea is to process the array from left to right. For each number at position j, we want to count how many previous numbers (at positions i < j) have a first digit that is coprime with the current number's last digit.

Since we only care about first digits of previous numbers, we can maintain a frequency array cnt[10] where cnt[d] stores how many numbers we've seen so far that have d as their first digit.

For each number x in the array:

1. We check its last digit (x % 10)
2. For each possible first digit value y (0-9), if we've seen numbers with that first digit before (cnt[y] > 0) and gcd(x % 10, y) == 1, then we've found cnt[y] beautiful pairs
3. After processing x as the second element of potential pairs, we add it to our count by incrementing cnt[first_digit_of_x]

This way, we process each element once and for each element we only check 10 possible digit values, giving us O(n) time complexity instead of O(n²).

Learn more about Math patterns.

Solution Approach

We implement the counting approach using an array cnt of size 10 to track the frequency of first digits from previously processed numbers.

Step-by-step implementation:

1. Initialize the counter array: Create cnt = [0] * 10 to store counts of first digits (indices 0-9).

2. Initialize answer: Set ans = 0 to accumulate the count of beautiful pairs.

3. Process each number: For each number x in nums:

   a. Find beautiful pairs with x as the second element:

   • Extract the last digit of x using x % 10
   • Iterate through all possible first digits y from 0 to 9
   • If cnt[y] > 0 (we've seen numbers with first digit y) and gcd(x % 10, y) == 1 (the digits are coprime), add cnt[y] to the answer

   b. Update the counter for future pairs:

   • Extract the first digit of x by converting to string: int(str(x)[0])
   • Increment cnt[first_digit] by 1

4. Return the result: After processing all numbers, return ans.

Example walkthrough:

If nums = [25, 37, 14]:

• Process 25: No previous numbers, so no pairs. Update cnt[2] = 1
• Process 37: Last digit is 7. Check if 7 is coprime with first digit 2 (from 25). Since gcd(7, 2) = 1, we found 1 pair. Update cnt[3] = 1
• Process 14: Last digit is 4. Check coprimality with first digits 2 and 3. gcd(4, 2) = 2 ≠ 1 (not coprime), gcd(4, 3) = 1 (coprime), so we found 1 more pair. Update cnt[1] = 1
• Total: 2 beautiful pairs

The algorithm efficiently counts beautiful pairs in O(n) time with O(1) space (since the cnt array has fixed size 10).

Example Walkthrough

Let's walk through the solution with nums = [11, 21, 12]:

Initial Setup:

• cnt = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0] (tracks frequency of first digits)
• ans = 0 (counts beautiful pairs)

Step 1: Process nums[0] = 11

• Last digit: 11 % 10 = 1
• Check all possible first digits (0-9) in cnt:
  • All counts are 0, so no pairs can be formed yet
• First digit of 11: int(str(11)[0]) = 1
• Update: cnt[1] = 1
• Current state: cnt = [0, 1, 0, 0, 0, 0, 0, 0, 0, 0], ans = 0

Step 2: Process nums[1] = 21

• Last digit: 21 % 10 = 1
• Check all possible first digits (0-9) in cnt:
  • cnt[1] = 1 (we have one number starting with 1)
  • Check if gcd(1, 1) = 1? Yes! So we add cnt[1] = 1 to answer
  • ans = 0 + 1 = 1
• First digit of 21: int(str(21)[0]) = 2
• Update: cnt[2] = 1
• Current state: cnt = [0, 1, 1, 0, 0, 0, 0, 0, 0, 0], ans = 1

Step 3: Process nums[2] = 12

• Last digit: 12 % 10 = 2
• Check all possible first digits (0-9) in cnt:
  • cnt[1] = 1: Check gcd(2, 1) = 1? Yes! Add 1 to answer
  • cnt[2] = 1: Check gcd(2, 2) = 2? No, not coprime
  • ans = 1 + 1 = 2
• First digit of 12: int(str(12)[0]) = 1
• Update: cnt[1] = 2
• Final state: cnt = [0, 2, 1, 0, 0, 0, 0, 0, 0, 0], ans = 2

Result: We found 2 beautiful pairs:

• Pair (0, 1): nums[0]=11 (first digit 1) and nums[1]=21 (last digit 1), gcd(1,1)=1 ✓
• Pair (0, 2): nums[0]=11 (first digit 1) and nums[2]=12 (last digit 2), gcd(1,2)=1 ✓

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × k) where n is the length of the array nums and k = 10 (constant representing possible digits 0-9).

• The outer loop iterates through all n elements in nums
• For each element, the inner loop iterates through 10 possible digits (0-9)
• Inside the inner loop, gcd(x % 10, y) operation takes O(log min(x % 10, y)) time, but since both values are single digits (0-9), this is effectively O(1)
• Converting x to string to get the first digit str(x)[0] takes O(log M) time where M is the maximum value in nums
• Overall: O(n × (10 + log M)) = O(n × (k + log M))

Space Complexity: O(k) where k = 10 (constant).

• The cnt array has a fixed size of 10 to store counts of first digits
• Converting integer x to string creates temporary space of O(log M) where M is the maximum value
• Overall: O(10 + log M) = O(k + log M)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Incorrect Order of Operations

Issue: A common mistake is updating the first_digit_count array before checking for beautiful pairs with the current number. This would incorrectly count a number pairing with itself.

Incorrect Implementation:

for current_num in nums:
    # WRONG: Updating count first
    current_first_digit = int(str(current_num)[0])
    first_digit_count[current_first_digit] += 1
  
    # Then checking pairs - this includes self-pairing!
    last_digit = current_num % 10
    for first_digit in range(10):
        if first_digit_count[first_digit] > 0 and gcd(last_digit, first_digit) == 1:
            beautiful_pairs_count += first_digit_count[first_digit]

Solution: Always check for pairs first, then update the counter. This ensures we only consider pairs where i < j.

Pitfall 2: Edge Case with GCD of Zero

Issue: When checking gcd(last_digit, first_digit), if first_digit is 0, the GCD calculation might behave unexpectedly. While gcd(n, 0) = n mathematically, this could lead to incorrect results if not handled properly.

Solution: Either handle zero explicitly or rely on Python's math.gcd which correctly handles gcd(n, 0) = n. Since we need gcd = 1 for coprime numbers, and gcd(n, 0) = n which is only 1 when n = 1, the logic works correctly.

Pitfall 3: Extracting First Digit of Single-Digit Numbers

Issue: For single-digit numbers, both first and last digits are the same. The string conversion str(current_num)[0] works correctly, but developers might overthink this case.

Example: For nums = [7], the first digit is 7 and last digit is 7. No pairs exist since we need at least two elements.

Solution: The current implementation handles this naturally - no special case needed.

Pitfall 4: Misunderstanding Pair Direction

Issue: Confusing which number provides the first digit and which provides the last digit. The problem states: first digit of nums[i] and last digit of nums[j] where i < j.

Incorrect Understanding: Checking first digit of nums[j] against last digit of nums[i].

Solution: Remember the pattern - as we iterate through the array, for each current number (acting as nums[j]), we use its last digit and check against first digits of all previous numbers (acting as nums[i]).