Skip to main content
Talentd

Number of Beautiful Pairs - Solution & Explanation

EasyArrayHash TableMathCounting20 min read
Practice this problem

Problem Statement

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 <= 100
  • 1 <= nums[i] <= 9999
  • nums[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.

The C solution defines a helper function gcd() to calculate the greatest common divisor of two integers. Another helper function firstDigit() is used to extract the first digit of a number. The main function calculates the total number of beautiful pairs by iterating over all pairs of indices and using the helper functions to check the condition for being coprime.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2), where n is the length of the input array, because we check each pair of elements once.

Space Complexity: O(1) as we use a constant amount of extra space.

Try this approach in the editor →

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.

The optimized C solution preprocesses the input array to create arrays for first and last digits. This avoids repeated calculations during the main pair-checking loop, making the code more efficient by performing these common calculations upfront.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2) — preprocessing takes O(n) and checking takes O(n^2).

Space Complexity: O(n) — additional space for first and last digit arrays.

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Brute Force Approach

Time Complexity: O(n^2), where n is the length of the input array, because we check each pair of elements once.

Space Complexity: O(1) as we use a constant amount of extra space.

Optimized Approach with Preprocessing

Time Complexity: O(n^2) — preprocessing takes O(n) and checking takes O(n^2).

Space Complexity: O(n) — additional space for first and last digit arrays.

Counting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Pair CheckingO(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

Video Solution

Leetcode Weekly contest 351 - Medium - Number of Beautiful Pairs • Prakhar Agrawal • 760 views views

Watch 5 more video solutions →

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.

Ready to solve this problem?

Practice Number of Beautiful Pairs with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays