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.
- Difficulty: Easy
- Topics: Arrays, Hash Table, Math, 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 <= 1001 <= nums[i] <= 9999nums[i] % 10 != 0
Hints for Number of Beautiful Pairs
Hint 1
The first digit comes from dividing by 10 until the number is below 10.
Hint 2
The last digit is just
% 10.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
- For index
i, stripnums[i]down to its leading digit by repeated division by 10. - For each
j > i, takenums[j] % 10. - Count the pair when
gcdof 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)withi < 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 countJava
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