LeetCode Problem 2748

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Math, Counting, Number Theory

Solution

LeetCode 2748 - Number of Beautiful Pairs

Problem Understanding

The problem gives us a 0-indexed integer array nums. We must count how many pairs of indices (i, j) satisfy 0 <= i < j < n and have the following property:

• Take the first digit of nums[i].
• Take the last digit of nums[j].
• The pair is considered beautiful if these two digits are coprime.

Two numbers are coprime when their greatest common divisor, gcd, equals 1.

For example, if nums[i] = 234, its first digit is 2. If nums[j] = 517, its last digit is 7. Since gcd(2, 7) = 1, this pair would be beautiful.

The input consists of:

• An array nums
• Each value is between 1 and 9999
• The array length is between 2 and 100

The output is a single integer representing the total number of beautiful pairs.

The constraints are very small. With at most 100 elements, there are at most:

$$\frac{100 \times 99}{2} = 4950$$

possible pairs. This immediately suggests that even checking every pair directly is computationally feasible.

Several details are important:

• Numbers may have different lengths, from one digit to four digits.
• We only care about the first digit of the left element and the last digit of the right element.
• The constraint nums[i] % 10 != 0 guarantees that the last digit is never 0.
• Single-digit numbers have the same first and last digit.
• Since digits range only from 1 to 9, gcd computations are extremely cheap.

Approaches

Brute Force

The most direct solution is to examine every valid pair (i, j).

For each pair:

1. Extract the first digit of nums[i].
2. Extract the last digit of nums[j].
3. Compute gcd(firstDigit, lastDigit).
4. If the gcd equals 1, increment the answer.

Since every possible pair is checked exactly once, this approach is obviously correct. Every beautiful pair contributes exactly one count, and no invalid pair is counted.

There are at most 4950 pairs, so the solution is already fast enough for the given constraints.

Key Insight

The crucial observation is that the constraints are very small.

Although one could build frequency tables based on leading digits and process numbers incrementally, such optimization is unnecessary. The brute-force pair enumeration already runs comfortably within the limits.

Therefore, the optimal practical solution is simply:

• Enumerate all pairs.
• Extract the required digits.
• Check coprimality using gcd.

This produces clean, simple, and efficient code.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Check every pair and test gcd
Optimal	O(n²)	O(1)	Same approach, constraints are small enough that no further optimization is needed

Algorithm Walkthrough

1. Initialize a variable answer to 0.
2. Iterate through every index i from 0 to n - 1.
3. Extract the first digit of nums[i]. Repeatedly divide the number by 10 until only one digit remains. The remaining digit is the first digit.
4. Iterate through every index j where j > i.
5. Extract the last digit of nums[j] using nums[j] % 10.
6. Compute gcd(firstDigit, lastDigit).
7. If the gcd equals 1, increment answer.
8. After all pairs have been processed, return answer.

Why it works

For every valid pair (i, j) with i < j, the algorithm examines that pair exactly once. It extracts precisely the digits specified in the problem statement and checks whether they are coprime using the mathematical definition of coprimality, namely gcd(a, b) == 1. Since every pair is considered and counted if and only if it satisfies the condition, the final count is exactly the number of beautiful pairs.

Python Solution

from typing import List
from math import gcd

class Solution:
    def countBeautifulPairs(self, nums: List[int]) -> int:
        def first_digit(num: int) -> int:
            while num >= 10:
                num //= 10
            return num

        n = len(nums)
        answer = 0

        for i in range(n):
            left_first = first_digit(nums[i])

            for j in range(i + 1, n):
                right_last = nums[j] % 10

                if gcd(left_first, right_last) == 1:
                    answer += 1

        return answer

The implementation follows the algorithm directly.

The helper function first_digit repeatedly divides a number by 10 until only the leading digit remains. This correctly handles numbers of any length from one to four digits.

The outer loop fixes the left element of the pair. The inner loop visits every valid right element with a larger index. For each pair, the last digit is obtained using the modulo operation % 10.

Python's built-in math.gcd function is then used to determine whether the two digits are coprime. Whenever the gcd equals 1, the pair is beautiful and the answer is incremented.

Finally, the accumulated count is returned.

Go Solution

package main

func gcd(a, b int) int {
	for b != 0 {
		a, b = b, a%b
	}
	return a
}

func firstDigit(num int) int {
	for num >= 10 {
		num /= 10
	}
	return num
}

func countBeautifulPairs(nums []int) int {
	n := len(nums)
	ans := 0

	for i := 0; i < n; i++ {
		leftFirst := firstDigit(nums[i])

		for j := i + 1; j < n; j++ {
			rightLast := nums[j] % 10

			if gcd(leftFirst, rightLast) == 1 {
				ans++
			}
		}
	}

	return ans
}

The Go version mirrors the Python implementation.

A helper function computes the gcd using the standard Euclidean algorithm. Another helper extracts the first digit by repeatedly dividing by 10. The nested loops enumerate all valid pairs and count those whose selected digits are coprime.

There are no special concerns regarding integer overflow because all values are extremely small. Go slices naturally handle the input array, and no additional data structures are required.

Worked Examples

Example 1

Input:

nums = [2, 5, 1, 4]

Pair	First Digit	Last Digit	GCD	Beautiful?
(0,1)	2	5	1	Yes
(0,2)	2	1	1	Yes
(0,3)	2	4	2	No
(1,2)	5	1	1	Yes
(1,3)	5	4	1	Yes
(2,3)	1	4	1	Yes

Running total:

Pair Processed	Answer
(0,1)	1
(0,2)	2
(0,3)	2
(1,2)	3
(1,3)	4
(2,3)	5

Final answer:

5

Example 2

Input:

nums = [11, 21, 12]

First digits:

11 -> 1
21 -> 2
12 -> 1

Last digits:

11 -> 1
21 -> 1
12 -> 2

Pair	First Digit	Last Digit	GCD	Beautiful?
(0,1)	1	1	1	Yes
(0,2)	1	2	1	Yes
(1,2)	2	2	2	No

Running total:

Pair Processed	Answer
(0,1)	1
(0,2)	2
(1,2)	2

Final answer:

2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n²)	Every pair of indices is examined once
Space	O(1)	Only a few variables are used

The array contains at most 100 elements, so there are at most 4950 pairs. Each pair requires only constant-time work consisting of digit extraction and a gcd computation on single-digit values. Therefore the total running time is quadratic in the number of elements, while the memory usage remains constant.

Test Cases

from typing import List

s = Solution()

assert s.countBeautifulPairs([2, 5, 1, 4]) == 5          # Example 1
assert s.countBeautifulPairs([11, 21, 12]) == 2          # Example 2

assert s.countBeautifulPairs([1, 1]) == 1               # Smallest valid array
assert s.countBeautifulPairs([2, 4]) == 0               # Not coprime
assert s.countBeautifulPairs([7, 9]) == 1               # Coprime digits

assert s.countBeautifulPairs([9999, 9999]) == 0         # gcd(9,9)=9
assert s.countBeautifulPairs([1111, 2222]) == 1         # gcd(1,2)=1

assert s.countBeautifulPairs([1, 2, 3]) == 3            # Every pair beautiful
assert s.countBeautifulPairs([2, 4, 6, 8]) == 0         # No pair beautiful

assert s.countBeautifulPairs([12, 34, 56, 78]) == 2     # Mixed results
assert s.countBeautifulPairs([1234, 5678, 9123]) == 2   # Multi-digit values

assert s.countBeautifulPairs([1] * 100) == 4950         # Maximum pair count

Test Summary

Test	Why
[2,5,1,4]	Verifies the first example
[11,21,12]	Verifies the second example
[1,1]	Smallest allowed input size
[2,4]	Pair is not coprime
[7,9]	Simple coprime pair
[9999,9999]	Largest digits with non-coprime result
[1111,2222]	Multi-digit first digit extraction
[1,2,3]	Every pair should be counted
[2,4,6,8]	No pair should be counted
[12,34,56,78]	Mixed beautiful and non-beautiful pairs
[1234,5678,9123]	Verifies extraction from larger numbers
[1] * 100	Maximum-size stress case

Edge Cases

Single-Digit Numbers

A single-digit number has the same first and last digit. An incorrect implementation might assume every number has multiple digits and accidentally remove the only digit during extraction. The helper function correctly stops once the number is less than 10, returning the digit itself.

Large Four-Digit Values

Values can be as large as 9999. A buggy implementation might incorrectly extract the leading digit using string indexing mistakes or arithmetic errors. Repeated division by 10 guarantees that 9999 correctly produces the first digit 9.

All Numbers Equal to 1

When every element is 1, every first digit and every last digit is also 1. Since gcd(1, 1) = 1, every possible pair is beautiful. The implementation correctly counts all n(n-1)/2 pairs because it explicitly checks every pair.

No Beautiful Pairs

Arrays such as [2, 4, 6, 8] produce only even first and last digits. Every gcd is greater than 1, so the answer should be 0. The algorithm handles this naturally because no pair satisfies the gcd condition, leaving the count unchanged.

Maximum Number of Pairs

With n = 100, there are 4950 possible pairs. Even in this worst case, the algorithm performs only a few thousand gcd checks, which is easily within the problem limits. The implementation therefore remains both simple and efficient.