Number of Beautiful Pairs — Easy Problem & Solution

A pair of indices i < j is beautiful when the first digit of nums[i] and the last digit of nums[j] are coprime — that is, their greatest common divisor is 1.

Difficulty: Easy
Topics: Arrays, Math, Hash Table, Counting, Number Theory
Asked at: Amazon, Google, Infosys
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A pair of indices i < j is beautiful when the first digit of nums[i] and the last digit of nums[j] are coprime — that is, their greatest common divisor is 1.

Return the number of beautiful pairs.

Example 1

Input: nums = [2,5,1,4]
Output: 5
Explanation: Every pair but `(0, 3)`, where `gcd(2, 4) = 2`.

Example 2

Input: nums = [11,21,12]
Output: 2
Explanation: `gcd(2, 2) = 2` rules out the pair `(1, 2)`.

Example 3

Input: nums = [7]
Output: 0
Explanation: A single element forms no pair.

Constraints

2 <= nums.length <= 100
1 <= nums[i] <= 9999
nums[i] % 10 != 0

How to solve Number of Beautiful Pairs

Extract each number's first and last digit, then count the ordered pairs whose digits are coprime.

Approach

For index i, strip nums[i] down to its leading digit by repeated division by 10.
For each j > i, take nums[j] % 10.
Count the pair when gcd of the two digits is 1.

Why it works

Both digits live in 1 … 9 — the constraint nums[i] % 10 != 0 is what keeps the last digit non-zero — so there are only 81 distinct digit pairs. That means counting digits and combining them gives an O(n + 81) solution; the quadratic scan here is simply enough at n <= 100.

Complexity

Time — O(n² · log) as written, or O(n + 81) by counting digits
Space — O(1)

Pitfalls

The first digit is the leading one, not nums[i] % 10.
Pairs are ordered by index: (i, j) with i < j, counted once.
gcd(1, x) is 1, so a leading or trailing 1 always pairs.

Reference solution

Python

from typing import List
from math import gcd

def countBeautifulPairs(nums: List[int]) -> int:
    n = len(nums)
    count = 0
    for i in range(n):
        first = nums[i]
        while first >= 10:
            first //= 10
        for j in range(i + 1, n):
            if gcd(first, nums[j] % 10) == 1:
                count += 1
    return count

JavaScript

var countBeautifulPairs = function(nums) {
    var gcd = function(a, b) {
        while (b !== 0) {
            var t = a % b;
            a = b;
            b = t;
        }
        return a;
    };
    var n = nums.length, count = 0;
    for (var i = 0; i < n; i++) {
        var first = nums[i];
        while (first >= 10) first = Math.floor(first / 10);
        for (var j = i + 1; j < n; j++) {
            if (gcd(first, nums[j] % 10) === 1) count++;
        }
    }
    return count;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue