Scale Engineer

Number of Beautiful Pairs

Easy
#2473Time: O(N^2). We have two nested loops that iterate through the array, resulting in a quadratic number of pairs to check. The operations inside the loop (digit extraction and GCD) are constant time since the digits are always between 1 and 9.Space: O(1). We only use a few variables for the loops and calculations, so the extra space required is constant.
Patterns
MathCountingNumber Theory
Data structures
ArrayHash Table

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly translates the problem statement into code. It involves checking every possible pair of indices (i, j) where i < j. For each pair, we extract the first digit of nums[i] and the last digit of nums[j] and then check if they are coprime.

Algorithm

  • Initialize a counter beautifulPairsCount to 0.
  • Use a nested loop to iterate through all pairs of indices (i, j) such that 0 <= i < j < nums.length.
  • For each pair (nums[i], nums[j]):
    • Extract the first digit of nums[i]. This can be done by repeatedly dividing the number by 10 until it is a single-digit number.
    • Extract the last digit of nums[j]. This is simply nums[j] % 10.
    • Calculate the greatest common divisor (GCD) of the two extracted digits using the Euclidean algorithm.
    • If the GCD is 1, it means the digits are coprime, so increment beautifulPairsCount.
  • After iterating through all valid pairs, return beautifulPairsCount.

Walkthrough

The brute-force solution uses two nested loops to generate all unique pairs of indices (i, j) where i is less than j. The outer loop runs from i = 0 to n-2 and the inner loop from j = i + 1 to n-1, where n is the length of the array. Inside the inner loop, for each pair of numbers nums[i] and nums[j], we find the first digit of nums[i] and the last digit of nums[j]. The first digit is found by repeatedly dividing the number by 10. The last digit is found using the modulo operator (% 10). We then compute their greatest common divisor (GCD). If the GCD is 1, the pair is beautiful, and we increment a counter. This process continues until all pairs have been checked.

class Solution {    public int countBeautifulPairs(int[] nums) {        int count = 0;        int n = nums.length;        for (int i = 0; i < n; i++) {            for (int j = i + 1; j < n; j++) {                int firstDigit = getFirstDigit(nums[i]);                int lastDigit = nums[j] % 10;                if (gcd(firstDigit, lastDigit) == 1) {                    count++;                }            }        }        return count;    }     private int getFirstDigit(int n) {        while (n >= 10) {            n /= 10;        }        return n;    }     private int gcd(int a, int b) {        while (b != 0) {            int temp = b;            b = a % b;            a = temp;        }        return a;    }}

Complexity

Time

O(N^2). We have two nested loops that iterate through the array, resulting in a quadratic number of pairs to check. The operations inside the loop (digit extraction and GCD) are constant time since the digits are always between 1 and 9.

Space

O(1). We only use a few variables for the loops and calculations, so the extra space required is constant.

Trade-offs

Pros

  • Simple to understand and implement.

  • Works well for the given constraints where nums.length <= 100.

Cons

  • Inefficient for large input sizes, as its time complexity is quadratic.

Solutions

class Solution {public  int countBeautifulPairs(int[] nums) {    int[] cnt = new int[10];    int ans = 0;    for (int x : nums) {      for (int y = 0; y < 10; ++y) {        if (cnt[y] > 0 && gcd(x % 10, y) == 1) {          ans += cnt[y];        }      }      while (x > 9) {        x /= 10;      }      ++cnt[x];    }    return ans;  }private  int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem