Number of Beautiful Pairs solution and explanation
5 more videos on this problem
Leetcode Weekly contest 351 - Medium - Number of Beautiful PairsPrakhar Agrawal · 3:50 · 760 views
Leetcode 2748 || Number of Beautiful Pairs || Leetcode Weekly Easy || cppKomal Pal · 8:51 · 592 views
Number of Beautiful Pairs Leet Code Weekly Contest 351 Join Link from commentsCoding Guru · 0:22 · 438 views
2748. Number of Beautiful Pairs (Leetcode Easy)Programming Live with Larry · 3:22 · 351 views
LeetCode Problem 2748: Number of Beautiful PairsTech Diet · 2:38 · 197 views
Number of Beautiful Pairs #LeetCode #java#googleinterview #micosoft #maths #amazoninterviewCodeVia · 3:57 · 95 views
The problem
You are given a 0-indexed integer array nums. A pair of indices i, j where 0 <= i < j < nums.length is called beautiful if the first digit of nums[i] and the last digit of nums[j] are coprime.
Return the total number of beautiful pairs in nums.
Two integers x and y are coprime if there is no integer greater than 1 that divides both of them. In other words, x and y are coprime if gcd(x, y) == 1, where gcd(x, y) is the greatest common divisor of x and y.
Example 1:
Input: nums = [2,5,1,4] Output: 5 Explanation: There are 5 beautiful pairs in nums: When i = 0 and j = 1: the first digit of nums[0] is 2, and the last digit of nums[1] is 5. We can confirm that 2 and 5 are coprime, since gcd(2,5) == 1. When i = 0 and j = 2: the first digit of nums[0] is 2, and the last digit of nums[2] is 1. Indeed, gcd(2,1) == 1. When i = 1 and j = 2: the first digit of nums[1] is 5, and the last digit of nums[2] is 1. Indeed, gcd(5,1) == 1. When i = 1 and j = 3: the first digit of nums[1] is 5, and the last digit of nums[3] is 4. Indeed, gcd(5,4) == 1. When i = 2 and j = 3: the first digit of nums[2] is 1, and the last digit of nums[3] is 4. Indeed, gcd(1,4) == 1. Thus, we return 5.
Example 2:
Input: nums = [11,21,12] Output: 2 Explanation: There are 2 beautiful pairs: When i = 0 and j = 1: the first digit of nums[0] is 1, and the last digit of nums[1] is 1. Indeed, gcd(1,1) == 1. When i = 0 and j = 2: the first digit of nums[0] is 1, and the last digit of nums[2] is 2. Indeed, gcd(1,2) == 1. Thus, we return 2.
Constraints:
2 <= nums.length <= 1001 <= nums[i] <= 9999nums[i] % 10 != 0
Approach overview
Problem Overview: You receive an array of integers. A pair (i, j) is considered beautiful when i < j and the first digit of nums[i] is coprime with the last digit of nums[j]. The task is to count how many such pairs exist.
Approach 1: Brute Force Pair Checking (O(n²) time, O(1) space)
The direct method checks every pair of indices (i, j) where i < j. Extract the first digit of nums[i] by repeatedly dividing by 10 until one digit remains, and compute the last digit of nums[j] using num % 10. For each pair, calculate gcd(firstDigit, lastDigit). If the result equals 1, the pair is beautiful. This approach uses simple iteration over the array and a standard GCD computation from number theory. It is easy to implement but inefficient for large arrays because it evaluates every possible pair.
Approach 2: Optimized Counting with Digit Frequency (O(n) time, O(1) space)
The key observation: only digits 1–9 can appear as the first digit, and last digits range from 0–9. Instead of comparing every pair, maintain a frequency count of the first digits seen so far while scanning the array from left to right. For each element nums[j], compute its last digit. Then check which previously seen first digits are coprime with this last digit. Add the corresponding frequencies to the answer. Finally, extract the first digit of nums[j] and update the frequency table.
This turns pair comparison into a small constant loop over digits 1–9. GCD checks are cheap, and you only store a fixed-size frequency array, which acts like a lightweight hash table. The algorithm effectively converts pair enumeration into a counting problem using ideas from counting. Time complexity becomes linear in the size of the input because each number is processed once.
Recommended for interviews: Start by explaining the brute force solution to show you understand the pair condition and how digits are extracted. Then move to the optimized counting approach. Interviewers expect the linear-time method because it recognizes the limited digit range and replaces pair iteration with frequency aggregation.
Approach 1: Brute Force Approach
This approach involves examining each pair (i, j) where 0 <= i < j < nums.length. For each pair, we extract the first digit of nums[i] and the last digit of nums[j], then check if these two digits are coprime.
To extract the first digit of a number, we repeatedly divide the number by 10 until it's less than 10. For the last digit, we take the modulo 10 of the number. Two numbers are coprime if their greatest common divisor (GCD) is 1.
import math
def first_digit(n):
while n >= 10:
n //= 10
return n
def count_beautiful_pairs(nums):
count = 0
for i in range(len(nums)):
first = first_digit(nums[i])
for j in range(i + 1, len(nums)):
last = nums[j] % 10
if math.gcd(first, last) == 1:
count += 1
return count
nums = [2, 5, 1, 4]
print(count_beautiful_pairs(nums)) # Output: 5import java.util.*;
public class BeautifulPairs {
static int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
static int firstDigit(int n) {
while (n >= 10) {
n /= 10;
}
return n;
}
static int countBeautifulPairs(int[] nums) {
int count = 0;
for (int i = 0; i < nums.length; i++) {
int first = firstDigit(nums[i]);
for (int j = i + 1; j < nums.length; j++) {
int last = nums[j] % 10;
if (gcd(first, last) == 1) {
count++;
}
}
}
return count;
}
public static void main(String[] args) {
int[] nums = {2, 5, 1, 4};
System.out.println(countBeautifulPairs(nums)); // Output: 5
}
}#include <iostream>
#include <vector>
#include <numeric>
int firstDigit(int n) {
while (n >= 10) {
n /= 10;
}
return n;
}
int countBeautifulPairs(const std::vector<int>& nums) {
int count = 0;
for (size_t i = 0; i < nums.size(); ++i) {
int first = firstDigit(nums[i]);
for (size_t j = i + 1; j < nums.size(); ++j) {
int last = nums[j] % 10;
if (std::gcd(first, last) == 1) {
++count;
}
}
}
return count;
}
int main() {
std::vector<int> nums = {2, 5, 1, 4};
std::cout << countBeautifulPairs(nums) << std::endl; // Output: 5
return 0;
}function gcd(a, b) {
while (b) {
const temp = b;
b = a % b;
a = temp;
}
return a;
}
function firstDigit(n) {
while (n >= 10) {
n = Math.floor(n / 10);
}
return n;
}
function countBeautifulPairs(nums) {
let count = 0;
for (let i = 0; i < nums.length; i++) {
const first = firstDigit(nums[i]);
for (let j = i + 1; j < nums.length; j++) {
const last = nums[j] % 10;
if (gcd(first, last) === 1) {
count++;
}
}
}
return count;
}
const nums = [2, 5, 1, 4];
console.log(countBeautifulPairs(nums)); // Output: 5;#include <stdio.h>
int gcd(int a, int b) {
while (b) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
int firstDigit(int n) {
while (n >= 10) {
n /= 10;
}
return n;
}
int countBeautifulPairs(int* nums, int numsSize) {
int count = 0;
for (int i = 0; i < numsSize; i++) {
int first = firstDigit(nums[i]);
for (int j = i + 1; j < numsSize; j++) {
int last = nums[j] % 10;
if (gcd(first, last) == 1) {
count++;
}
}
}
return count;
}
int main() {
int nums[] = {2, 5, 1, 4};
int numsSize = sizeof(nums) / sizeof(nums[0]);
int result = countBeautifulPairs(nums, numsSize);
printf("%d\n", result); // Output: 5
return 0;
}using System;
public class BeautifulPairs {
public static int GCD(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
public static int FirstDigit(int n) {
while (n >= 10) {
n /= 10;
}
return n;
}
public static int CountBeautifulPairs(int[] nums) {
int count = 0;
for (int i = 0; i < nums.Length; i++) {
int first = FirstDigit(nums[i]);
for (int j = i + 1; j < nums.Length; j++) {
int last = nums[j] % 10;
if (GCD(first, last) == 1) {
count++;
}
}
}
return count;
}
public static void Main() {
int[] nums = { 2, 5, 1, 4 };
Console.WriteLine(CountBeautifulPairs(nums)); // Output: 5
}
}The Python solution leverages the math.gcd function for computing the GCD. We use a helper function first_digit() to get the first digit. The double loop structure allows us to check each pair of indices for coprimality.
Time Complexity: O(n^2) due to nested iterations over pairs of elements.
Space Complexity: O(1), considering no additional space utilization based on input size.
Approach 2: Optimized Approach with Preprocessing
This approach preprocesses both the first digits and last digits of all numbers beforehand, saving this information in separate arrays. We then iterate over pairs to determine the total number of beautiful pairs. By preprocessing, we avoid recomputing the first and last digits multiple times.
import math
def first_digit(n):
while n >= 10:
n //= 10
return n
def count_beautiful_pairs(nums):
first_digits = [first_digit(num) for num in nums]
last_digits = [num % 10 for num in nums]
count = 0
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if math.gcd(first_digits[i], last_digits[j]) == 1:
count += 1
return count
nums = [2, 5, 1, 4]
print(count_beautiful_pairs(nums)) # Output: 5import java.util.*;
public class BeautifulPairs {
static int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
static int firstDigit(int n) {
while (n >= 10) {
n /= 10;
}
return n;
}
static int countBeautifulPairs(int[] nums) {
int[] firstDigits = new int[nums.length];
int[] lastDigits = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
firstDigits[i] = firstDigit(nums[i]);
lastDigits[i] = nums[i] % 10;
}
int count = 0;
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (gcd(firstDigits[i], lastDigits[j]) == 1) {
count++;
}
}
}
return count;
}
public static void main(String[] args) {
int[] nums = {2, 5, 1, 4};
System.out.println(countBeautifulPairs(nums)); // Output: 5
}
}#include <iostream>
#include <vector>
#include <numeric>
int firstDigit(int n) {
while (n >= 10) {
n /= 10;
}
return n;
}
int countBeautifulPairs(const std::vector<int>& nums) {
std::vector<int> firstDigits(nums.size());
std::vector<int> lastDigits(nums.size());
for (size_t i = 0; i < nums.size(); ++i) {
firstDigits[i] = firstDigit(nums[i]);
lastDigits[i] = nums[i] % 10;
}
int count = 0;
for (size_t i = 0; i < nums.size(); ++i) {
for (size_t j = i + 1; j < nums.size(); ++j) {
if (std::gcd(firstDigits[i], lastDigits[j]) == 1) {
count++;
}
}
}
return count;
}
int main() {
std::vector<int> nums = {2, 5, 1, 4};
std::cout << countBeautifulPairs(nums) << std::endl; // Output: 5
return 0;
}function gcd(a, b) {
while (b) {
const temp = b;
b = a % b;
a = temp;
}
return a;
}
function firstDigit(n) {
while (n >= 10) {
n = Math.floor(n / 10);
}
return n;
}
function countBeautifulPairs(nums) {
const firstDigits = nums.map(n => firstDigit(n));
const lastDigits = nums.map(n => n % 10);
let count = 0;
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (gcd(firstDigits[i], lastDigits[j]) === 1) {
count++;
}
}
}
return count;
}
const nums = [2, 5, 1, 4];
console.log(countBeautifulPairs(nums)); // Output: 5;#include <stdio.h>
int gcd(int a, int b) {
while (b) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
int firstDigit(int n) {
while (n >= 10) {
n /= 10;
}
return n;
}
int countBeautifulPairs(int* nums, int numsSize) {
int firstDigits[numsSize];
int lastDigits[numsSize];
for (int i = 0; i < numsSize; ++i) {
firstDigits[i] = firstDigit(nums[i]);
lastDigits[i] = nums[i] % 10;
}
int count = 0;
for (int i = 0; i < numsSize; ++i) {
for (int j = i + 1; j < numsSize; ++j) {
if (gcd(firstDigits[i], lastDigits[j]) == 1) {
count++;
}
}
}
return count;
}
int main() {
int nums[] = {2, 5, 1, 4};
int numsSize = sizeof(nums) / sizeof(nums[0]);
int result = countBeautifulPairs(nums, numsSize);
printf("%d\n", result); // Output: 5
return 0;
}using System;
using System.Linq;
public class BeautifulPairs {
public static int GCD(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
public static int FirstDigit(int n) {
while (n >= 10) {
n /= 10;
}
return n;
}
public static int CountBeautifulPairs(int[] nums) {
int[] firstDigits = nums.Select(FirstDigit).ToArray();
int[] lastDigits = nums.Select(num => num % 10).ToArray();
int count = 0;
for (int i = 0; i < nums.Length; i++) {
for (int j = i + 1; j < nums.Length; j++) {
if (GCD(firstDigits[i], lastDigits[j]) == 1) {
count++;
}
}
}
return count;
}
public static void Main() {
int[] nums = { 2, 5, 1, 4 };
Console.WriteLine(CountBeautifulPairs(nums)); // Output: 5
}
}This Python implementation preprocesses the first and last digits, storing them in lists. This preprocessing reduces repetitive work during the main loop that checks pairs for coprimality.
Time Complexity: O(n^2) for pair checking with O(n) preprocessing.
Space Complexity: O(n) for storing precomputed digits.
Approach 3: Counting
We can use an array cnt of length 10 to record the count of the first digit of each number.
Iterate through the array nums. For each number x, we enumerate each digit y from 0 to 9. If cnt[y] is not 0 and gcd(x \mod 10, y) = 1, then the answer is incremented by cnt[y]. Then, we increment the count of the first digit of x by 1.
After the iteration, return the answer.
The time complexity is O(n times (k + log M)), and the space complexity is O(k + log M). Here, n is the length of the array nums, while k and M respectively represent the number of distinct numbers and the maximum value in the array nums.
function countBeautifulPairs(nums: number[]): number {
const cnt: number[] = Array(10).fill(0);
let ans = 0;
for (let x of nums) {
for (let y = 0; y < 10; ++y) {
if (cnt[y] > 0 && gcd(x % 10, y) === 1) {
ans += cnt[y];
}
}
while (x > 9) {
x = Math.floor(x / 10);
}
++cnt[x];
}
return ans;
}
function gcd(a: number, b: number): number {
if (b === 0) {
return a;
}
return gcd(b, a % b);
}func countBeautifulPairs(nums []int) (ans int) {
cnt := [10]int{}
for _, x := range nums {
for y := 0; y < 10; y++ {
if cnt[y] > 0 && gcd(x%10, y) == 1 {
ans += cnt[y]
}
}
for x > 9 {
x /= 10
}
cnt[x]++
}
return
}
func gcd(a, b int) int {
if b == 0 {
return a
}
return gcd(b, a%b)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: Space Complexity: |
| Optimized Approach with Preprocessing | Time Complexity: Space Complexity: |
| Counting | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Checking | O(n²) | O(1) | Small input sizes or when first learning the problem |
| Digit Frequency Counting (Optimized) | O(n) | O(1) | Preferred solution for interviews and large arrays |
Frequently asked questions
Is Number of Beautiful Pairs easy or hard?
Number of Beautiful Pairs is categorized as an Easy problem on LeetCode with about a 52% acceptance rate. The brute force approach is straightforward, while the optimized solution requires recognizing the limited digit range and applying counting with GCD checks.
How to solve Number of Beautiful Pairs in O(n)?
Scan the array from left to right and maintain a frequency array for first digits encountered so far. For each number, compute its last digit and count how many stored first digits are coprime with it using a GCD check. Add those counts to the answer and then update the frequency with the current number’s first digit.
What is the best approach for Number of Beautiful Pairs?
The optimized counting approach is the best solution. Iterate through the array while keeping a frequency count of previously seen first digits. For each number, check which digits are coprime with its last digit and add their frequencies. This reduces pair comparison from O(n²) to O(n).
Is Number of Beautiful Pairs asked at Google/Amazon/Meta?
Problems involving digit manipulation, GCD, and pair counting appear frequently in coding interviews at companies like Amazon and Google. This problem tests number theory basics and the ability to optimize brute-force pair checks using counting techniques.
What data structure is used in Number of Beautiful Pairs?
The optimized solution mainly uses a fixed-size frequency array that behaves like a lightweight hash table. It stores counts of first digits (1–9) encountered earlier, enabling constant-time lookups when evaluating new elements.
What is the time complexity of Number of Beautiful Pairs?
The optimal solution runs in O(n) time because each number in the array is processed once. For every element, only a constant number of digit checks (1–9) are performed. Space complexity remains O(1) since only a small frequency array of digits is stored.
Number of Beautiful Pairs Python or Java solution approach?
Both Python and Java implementations follow the same idea: extract the last digit using modulo, compute the first digit using division, and maintain a frequency array for digits. The loop checks coprime digits using a GCD function and accumulates the result in linear time.