2748. Number of Beautiful Pairs

EasyArrayMathNumber Theory
Leetcode Link

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following is equvalent to O(3*2^n + n^3 + n!+ log n)?

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:

  1. Initialize a count array cnt with 10 zeros, corresponding to the digits from 0 to 9.
  2. Initialize a variable ans to 0, which will hold the count of the beautiful pairs.

For every number x in nums:

  1. Extract the last digit of x by calculating x % 10.

  2. 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 and y are coprime.
    • If they are coprime, increment ans by the count of numbers (cnt[y]) that had y as their first digit.

  3. Convert x to a string and take the first character, convert it back to an integer, and increment the respective count in cnt.

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which two pointer technique does Quick Sort use?

Example Walkthrough

Let's walk through a small example to illustrate the solution approach. Suppose our input array nums is [12, 35, 46, 57, 23].

  1. We initialize our count array cnt with 10 zeros: cnt = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0].
  2. 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 to cnt[1] because 1 is the first digit.
    • The cnt array becomes [0, 1, 0, 0, 0, 0, 0, 0, 0, 0].

  • 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) is 1, they are coprime, so we increment ans by the count of numbers with the first digit 1, which is 1.
    • ans becomes 1.
    • We add 1 to cnt[3] for the first digit of 35.
    • The cnt array becomes [0, 1, 0, 1, 0, 0, 0, 0, 0, 0].

  • For num 46:

    • The last digit is 6.
    • We check against first digits 1 and 3 (from 12 and 35).
    • gcd(6, 1) is 1, so they are coprime, increment ans by cnt[1] which is 1.
    • gcd(6, 3) is 3, so 6 and 3 are not coprime, do nothing for cnt[3].
    • ans becomes 2.
    • We add 1 to cnt[4] for the first digit of 46.
    • The cnt array becomes [0, 1, 0, 1, 1, 0, 0, 0, 0, 0].

  • For num 57:

    • The last digit is 7.
    • We check against first digits 1, 3, and 4.
    • gcd(7, 1), gcd(7, 3), gcd(7, 4) are all 1, so 7 is coprime with 1, 3, and 4.
    • Increment ans by cnt[1] + cnt[3] + cnt[4] which is 1 + 1 + 1 = 3.
    • ans becomes 5.
    • We add 1 to cnt[5] for the first digit of 57.
    • The cnt array becomes [0, 1, 0, 1, 1, 1, 0, 0, 0, 0].

  • For num 23:

    • The last digit is 3.
    • We check against first digits 1, 3, 4, and 5.
    • gcd(3, 1) is 1, so they are coprime, increment ans by cnt[1] which is 1.
    • gcd(3, 3) is 3, so not coprime with itself, do nothing for cnt[3].
    • gcd(3, 4) is 1, so they are coprime, increment ans by cnt[4] which is 1.
    • gcd(3, 5) is 1, so they are coprime, increment ans by cnt[5] which is 1.
    • ans becomes 5 + 1 + 1 + 1 = 8.
    • We add 1 to cnt[2] for the first digit of 23.
    • The cnt array becomes [0, 1, 1, 1, 1, 1, 0, 0, 0, 0].

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
Not Sure What to Study? Take the 2-min Quiz：

Which of the following is a good use case for backtracking?

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 of O(n) to the complexity.
  • Inside the loop, we execute a fixed number of iterations (10, for the range of y from 0 to 9), checking the greatest common divisor (gcd) of a pair of single digits. Since both the number of iterations and the gcd operation on single-digit numbers are constant-time operations, the loop inside does not depend on n 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 of x.

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 of 10, which does not depend on the size of the input list nums.
  • 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.

Fast Track Your Learning with Our Quick Skills Quiz:

Which algorithm should you use to find a node that is close to the root of the tree?

Recommended Readings

Math Basics

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 - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

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

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫