Number of Beautiful Pairs

Easy
994.

Number of Beautiful Pairs

Number of Beautiful Pairs is an easy coding problem on arrays, hash table and math, asked in Amazon, Google and Infosys interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var countBeautifulPairs = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Number of Beautiful Pairs — Solution in Python, Java & C++

Number of Beautiful Pairs solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Number of Beautiful Pairs is an easy coding problem on arrays, hash table and math, asked in Amazon, Google and Infosys interviews.

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

Hints for Number of Beautiful Pairs

  1. Hint 1

    The first digit comes from dividing by 10 until the number is below 10.

  2. Hint 2

    The last digit is just % 10.

  3. Hint 3

    Both digits are in 1 … 9, so the gcd is cheap; a 9 × 9 table also works.

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

  1. For index i, strip nums[i] down to its leading digit by repeated division by 10.
  2. For each j > i, take nums[j] % 10.
  3. 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

Java

private static int bpGcd(int a, int b) {
    while (b != 0) {
        int t = a % b;
        a = b;
        b = t;
    }
    return a;
}

public static int countBeautifulPairs(int[] nums) {
    int n = nums.length, count = 0;
    for (int i = 0; i < n; i++) {
        int first = nums[i];
        while (first >= 10) first /= 10;
        for (int j = i + 1; j < n; j++) {
            if (bpGcd(first, nums[j] % 10) == 1) count++;
        }
    }
    return count;
}

C++

static int bpGcd(int a, int b) {
    while (b != 0) {
        int t = a % b;
        a = b;
        b = t;
    }
    return a;
}

int countBeautifulPairs(vector<int>& nums) {
    int n = (int) nums.size(), count = 0;
    for (int i = 0; i < n; i++) {
        int first = nums[i];
        while (first >= 10) first /= 10;
        for (int j = i + 1; j < n; j++) {
            if (bpGcd(first, nums[j] % 10) == 1) count++;
        }
    }
    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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets