2748. Number of Beautiful Pairs
Problem Description
The LeetCode problem provides an array nums
, indexed from 0. We need to find all the "beautiful pairs" in this array. A pair of indices (i, j)
is considered beautiful if the first digit of nums[i]
and the last digit of nums[j]
are coprime. Two numbers are coprime if their greatest common divisor (gcd) is 1, meaning they do not have any prime factors in common besides 1.
To solve the problem, we have to count each such pair where i < j
.
Intuition
To solve this problem efficiently, we recognize that there are only 10 possible digits (0 through 9), so it's possible to count occurrences of leading and trailing digits without having to compare every possible pair (which would be inefficient). The solution provided keeps track of the count of leading digits encountered so far in a count array cnt
, as we iterate through the array.
For each number x
in nums
, we check if the last digit of x
is coprime with each digit we've seen as a first digit, using the gcd function. If they are coprime, we add the count recorded for that first digit to our answer ans
, which accumulates the total number of beautiful pairs. After checking against all first digits we've seen, we then record the first digit of x in our cnt
count array, incrementing the count for that digit, which will be used for subsequent numbers in nums
.
This approach ensures that we are only iterating through the array once and are maintaining a constant-size array to track the counts of first digits, leading to a time-efficient solution.
Learn more about Math patterns.
Solution Approach
The solution uses a count array cnt
of size 10 (since we have 10 digits from 0 to 9) to keep a tally on the number of times a digit appears as the first digit of a number in nums
. Furthermore, it leverages the Greatest Common Divisor (gcd) to check for coprimality.
Here's a step-by-step breakdown of the algorithm:
- Initialize a count array
cnt
with 10 zeros, corresponding to the digits from 0 to 9. - Initialize a variable
ans
to 0, which will hold the count of the beautiful pairs.
For every number x
in nums
:
-
Extract the last digit of
x
by calculatingx % 10
. -
For every possible first digit
y
ranging from 0 to 9:- Check if we have previously encountered
y
as a first digit (cnt[y] > 0
). - Calculate
gcd(x % 10, y)
. If it is 1,x
's last digit andy
are coprime. - If they are coprime, increment
ans
by the count of numbers (cnt[y]
) that hady
as their first digit.
- Check if we have previously encountered
-
Convert
x
to a string and take the first character, convert it back to an integer, and increment the respective count incnt
.
By using this calculation method, only a single pass through the nums
array is needed, and we avoid comparing every pair of numbers. Complexity is reduced from potentially O(n^2) to O(n) because we're only performing a constant amount of work for each of the n
elements in nums
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach. Suppose our input array nums
is [12, 35, 46, 57, 23]
.
- We initialize our count array
cnt
with 10 zeros:cnt = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
. - We initialize our variable
ans
to 0.
Now for each number in nums
:
-
For num
12
:- The last digit is
2
(12 % 10
). - No other numbers have been processed yet, so we add
1
tocnt[1]
because1
is the first digit. - The
cnt
array becomes[0, 1, 0, 0, 0, 0, 0, 0, 0, 0]
.
- The last digit is
-
For num
35
:- The last digit is
5
(35 % 10
). - We check against all first digits we've seen so far, which is only
1
. gcd(5, 1)
is1
, they are coprime, so we incrementans
by the count of numbers with the first digit1
, which is1
.ans
becomes1
.- We add
1
tocnt[3]
for the first digit of35
. - The
cnt
array becomes[0, 1, 0, 1, 0, 0, 0, 0, 0, 0]
.
- The last digit is
-
For num
46
:- The last digit is
6
. - We check against first digits
1
and3
(from12
and35
). gcd(6, 1)
is1
, so they are coprime, incrementans
bycnt[1]
which is1
.gcd(6, 3)
is3
, so6
and3
are not coprime, do nothing forcnt[3]
.ans
becomes2
.- We add
1
tocnt[4]
for the first digit of46
. - The
cnt
array becomes[0, 1, 0, 1, 1, 0, 0, 0, 0, 0]
.
- The last digit is
-
For num
57
:- The last digit is
7
. - We check against first digits
1
,3
, and4
. gcd(7, 1)
,gcd(7, 3)
,gcd(7, 4)
are all1
, so7
is coprime with1
,3
, and4
.- Increment
ans
bycnt[1] + cnt[3] + cnt[4]
which is1 + 1 + 1 = 3
. ans
becomes5
.- We add
1
tocnt[5]
for the first digit of57
. - The
cnt
array becomes[0, 1, 0, 1, 1, 1, 0, 0, 0, 0]
.
- The last digit is
-
For num
23
:- The last digit is
3
. - We check against first digits
1
,3
,4
, and5
. gcd(3, 1)
is1
, so they are coprime, incrementans
bycnt[1]
which is1
.gcd(3, 3)
is3
, so not coprime with itself, do nothing forcnt[3]
.gcd(3, 4)
is1
, so they are coprime, incrementans
bycnt[4]
which is1
.gcd(3, 5)
is1
, so they are coprime, incrementans
bycnt[5]
which is1
.ans
becomes5 + 1 + 1 + 1 = 8
.- We add
1
tocnt[2]
for the first digit of23
. - The
cnt
array becomes[0, 1, 1, 1, 1, 1, 0, 0, 0, 0]
.
- The last digit is
After processing all the numbers, we have gone through the array once, and the total count of beautiful pairs ans
is 8
.
Solution Implementation
1from typing import List
2from math import gcd
3
4class Solution:
5 def count_beautiful_pairs(self, nums: List[int]) -> int:
6 # Initialize count array with zeroes for each digit from 0 to 9
7 count = [0] * 10
8
9 # Initialize the answer to 0, which will hold the number of beautiful pairs
10 answer = 0
11
12 # Iterate over each number in the input list
13 for number in nums:
14 # Check each digit from 0 to 9
15 for digit in range(10):
16 # If there is a previously encountered number whose last digit has GCD=1 with current last digit of 'number'
17 if count[digit] and gcd(number % 10, digit) == 1:
18 # Increment 'answer' by the count of that digit since it forms a beautiful pair
19 answer += count[digit]
20
21 # Increment the count of the first digit of 'number'
22 count[int(str(number)[0])] += 1
23
24 # Return the total count of beautiful pairs
25 return answer
26
1class Solution {
2 public int countBeautifulPairs(int[] nums) {
3 // An array to count the occurrences of the last digits encountered.
4 int[] countLastDigits = new int[10];
5
6 // Initialize a variable to keep track of the number of beautiful pairs.
7 int beautifulPairs = 0;
8
9 // Iterate over each number in the input array.
10 for (int number : nums) {
11 // For each digit from 0 to 9, check if we have seen it before as a last digit.
12 for (int y = 0; y < 10; ++y) {
13 // If we have seen this last digit and the gcd of current number's last digit
14 // and y is 1, increment the count of beautiful pairs by the number of times we've seen y.
15 if (countLastDigits[y] > 0 && gcd(number % 10, y) == 1) {
16 beautifulPairs += countLastDigits[y];
17 }
18 }
19 // Reduce the current number to its last digit.
20 while (number > 9) {
21 number /= 10;
22 }
23 // Increment the count of the last digit of the current number.
24 ++countLastDigits[number];
25 }
26
27 // Return the total count of beautiful pairs found.
28 return beautifulPairs;
29 }
30
31 // A helper method to calculate the greatest common divisor of two numbers.
32 private int gcd(int a, int b) {
33 // If b is zero, then a is the gcd. Otherwise, recursively call gcd with b and a % b.
34 return b == 0 ? a : gcd(b, a % b);
35 }
36}
37
1#include <vector>
2#include <numeric> // For std::gcd
3
4class Solution {
5public:
6 // Function to count beautiful pairs
7 // A beautiful pair is defined such that the greatest common divisor (gcd) of the
8 // least significant digit of one number and any digit of another number is 1
9 int countBeautifulPairs(std::vector<int>& nums) {
10 // Count array to keep track of the least significant digits of the numbers
11 int countDigits[10] = {}; // Initializing all elements to 0
12 int beautifulPairs = 0; // Initialize beautiful pairs count
13
14 // Loop through all numbers in the vector
15 for (int number : nums) {
16 // Check against all digits from 0 to 9
17 for (int digit = 0; digit < 10; ++digit) {
18 // If the count of digits is not zero and
19 // the gcd of the number's least significant digit and current digit is 1,
20 // increment the beautifulPairs by the count of that digit
21 if (countDigits[digit] && std::gcd(number % 10, digit) == 1) {
22 beautifulPairs += countDigits[digit];
23 }
24 }
25 // Reduce the number to its least significant digit
26 while (number > 9) {
27 number /= 10;
28 }
29 // Increment the count of the least significant digit
30 ++countDigits[number];
31 }
32
33 // Return the total count of beautiful pairs
34 return beautifulPairs;
35 }
36};
37
1/**
2 * Calculates the count of beautiful pairs in the array.
3 * A pair (i, j) is considered beautiful if the GCD of the last digit of nums[i] and nums[j] is 1,
4 * and i < j.
5 * @param nums - array of numbers
6 * @returns the count of beautiful pairs
7 */
8function countBeautifulPairs(nums: number[]): number {
9 // Initialize an array to keep count of the last digit frequency
10 const lastDigitCount: number[] = Array(10).fill(0);
11 let beautifulPairsCount = 0;
12
13 // Loop through each number in the nums array
14 for (let num of nums) {
15 // Check against all possible last digits
16 for (let digit = 0; digit < 10; ++digit) {
17 // If there's a number with this last digit and their GCD of last digits is 1, count it
18 if (lastDigitCount[digit] > 0 && gcd(num % 10, digit) === 1) {
19 beautifulPairsCount += lastDigitCount[digit];
20 }
21 }
22 // Reduce the number to its last digit
23 while (num > 9) {
24 num = Math.floor(num / 10);
25 }
26 // Increment the count for this last digit
27 ++lastDigitCount[num];
28 }
29 // Return the total count of beautiful pairs
30 return beautifulPairsCount;
31}
32
33/**
34 * Recursively calculates the Greatest Common Divisor (GCD) of two numbers using Euclid's algorithm.
35 * @param a - first number
36 * @param b - second number
37 * @returns the GCD of a and b
38 */
39function gcd(a: number, b: number): number {
40 // Base case: if second number is 0, return the first number
41 if (b === 0) {
42 return a;
43 }
44 // Recursive case: return the GCD of b and the remainder of a divided by b
45 return gcd(b, a % b);
46}
47
Time and Space Complexity
Time Complexity
The time complexity of the given code is O(n)
where n
is the length of the input list nums
. The analysis is as follows:
- We have a single loop that iterates over each element of
nums
, which contributes a factor ofO(n)
to the complexity. - Inside the loop, we execute a fixed number of iterations (10, for the range of
y
from0
to9
), checking the greatest common divisor (gcd
) of a pair of single digits. Since both the number of iterations and thegcd
operation on single-digit numbers are constant-time operations, the loop inside does not depend onn
and thus contributes a constant factor,O(1)
, per each outer loop iteration. - Updating the count array
cnt
also operates in constant time,O(1)
, because it accesses a predetermined index determined by the first digit ofx
.
Hence, combining these, the time complexity is O(n) * O(1) = O(n)
.
Space Complexity
The space complexity of the code is O(1)
which is a constant space overhead, regardless of the input size. This is explained as follows:
- The
cnt
array has a fixed length of10
, which does not depend on the size of the input listnums
. - The
ans
variable is just a single integer counter.
As neither of these two grows with the size of the input nums
, the space complexity of the algorithm is constant.
Learn more about how to find time and space complexity quickly using problem constraints.
What's the output of running the following function using input 56
?
1KEYBOARD = {
2 '2': 'abc',
3 '3': 'def',
4 '4': 'ghi',
5 '5': 'jkl',
6 '6': 'mno',
7 '7': 'pqrs',
8 '8': 'tuv',
9 '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13 def dfs(path, res):
14 if len(path) == len(digits):
15 res.append(''.join(path))
16 return
17
18 next_number = digits[len(path)]
19 for letter in KEYBOARD[next_number]:
20 path.append(letter)
21 dfs(path, res)
22 path.pop()
23
24 res = []
25 dfs([], res)
26 return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2 '2', "abc".toCharArray(),
3 '3', "def".toCharArray(),
4 '4', "ghi".toCharArray(),
5 '5', "jkl".toCharArray(),
6 '6', "mno".toCharArray(),
7 '7', "pqrs".toCharArray(),
8 '8', "tuv".toCharArray(),
9 '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13 List<String> res = new ArrayList<>();
14 dfs(new StringBuilder(), res, digits.toCharArray());
15 return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19 if (path.length() == digits.length) {
20 res.add(path.toString());
21 return;
22 }
23 char next_digit = digits[path.length()];
24 for (char letter : KEYBOARD.get(next_digit)) {
25 path.append(letter);
26 dfs(path, res, digits);
27 path.deleteCharAt(path.length() - 1);
28 }
29}
30
1const KEYBOARD = {
2 '2': 'abc',
3 '3': 'def',
4 '4': 'ghi',
5 '5': 'jkl',
6 '6': 'mno',
7 '7': 'pqrs',
8 '8': 'tuv',
9 '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13 let res = [];
14 dfs(digits, [], res);
15 return res;
16}
17
18function dfs(digits, path, res) {
19 if (path.length === digits.length) {
20 res.push(path.join(''));
21 return;
22 }
23 let next_number = digits.charAt(path.length);
24 for (let letter of KEYBOARD[next_number]) {
25 path.push(letter);
26 dfs(digits, path, res);
27 path.pop();
28 }
29}
30
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!