# Number of Beautiful Pairs
**Difficulty:** EASY
[External](https://leetcode.com/problems/number-of-beautiful-pairs)
Canonical: https://scaleengineer.com/dsa/problems/number-of-beautiful-pairs
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Counting](https://scaleengineer.com/dsa/patterns/counting), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory)
**Data structures:** Array, Hash Table
---
## 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 <= 100`
* `1 <= nums[i] <= 9999`
* `nums[i] % 10 != 0`

# Approaches
## Brute-Force Iteration
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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`.

## Single Pass with Frequency Count
An optimized approach is to iterate through the array just once. We can use a frequency map (or a simple array since digits are 1-9) to keep track of the first digits of numbers we have already processed. For each new number, we can quickly find how many beautiful pairs it forms with the numbers seen so far.
**Time:** O(N). We iterate through the `nums` array once. The inner loop runs a constant 9 times for each number. All other operations inside the loop are constant time. · **Space:** O(1). We use an auxiliary array `firstDigitCounts` of a fixed size 10, which does not depend on the input size.
**Pros:** Highly efficient with a linear time complexity.; Scales well even for much larger inputs than specified in the constraints.
**Cons:** Slightly more complex to reason about compared to the brute-force approach.
### Explanation
This approach avoids the O(N^2) complexity by making a single pass over the array. The key idea is that as we iterate to an element `nums[j]`, we can count how many preceding elements `nums[i]` (where `i < j`) form a beautiful pair with it. To do this efficiently, we maintain a frequency array, `firstDigitCounts`, of size 10. `firstDigitCounts[d]` will store how many numbers we have seen so far that have `d` as their first digit.

When we are at `nums[j]`, we get its last digit, `ld`. Then, we iterate through all possible first digits `fd` from 1 to 9. If `gcd(fd, ld) == 1`, we know that `nums[j]` forms a beautiful pair with all the previously seen numbers whose first digit is `fd`. We add `firstDigitCounts[fd]` to our total count. After we have tallied the pairs for `nums[j]`, we update the frequency array by finding the first digit of `nums[j]` and incrementing its count. This ensures that `nums[j]` is considered for subsequent elements.

```java
class Solution {
    public int countBeautifulPairs(int[] nums) {
        int count = 0;
        int[] firstDigitCounts = new int[10]; // To store frequency of first digits (1-9)

        for (int num : nums) {
            int lastDigit = num % 10;
            for (int firstDigit = 1; firstDigit <= 9; firstDigit++) {
                if (firstDigitCounts[firstDigit] > 0 && gcd(firstDigit, lastDigit) == 1) {
                    count += firstDigitCounts[firstDigit];
                }
            }
            
            int currentFirstDigit = getFirstDigit(num);
            firstDigitCounts[currentFirstDigit]++;
        }
        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;
    }
}
```
### Algorithm
- Initialize a counter `beautifulPairsCount` to 0.
- Initialize a frequency array `firstDigitCounts` of size 10 to all zeros. This array will store the counts of the first digits of numbers encountered so far.
- Iterate through each `num` in the input array `nums`.
- For the current `num`:
  - Get its last digit, `ld = num % 10`.
  - Iterate through all possible first digits `fd` from 1 to 9.
  - If `gcd(fd, ld) == 1`, it means any number seen previously with `fd` as its first digit forms a beautiful pair. Add the count `firstDigitCounts[fd]` to `beautifulPairsCount`.
- After checking for pairs, update the frequency map for the current number:
  - Get the first digit of the current `num`, `currentFd`.
  - Increment `firstDigitCounts[currentFd]`.
- After iterating through all numbers in `nums`, return `beautifulPairsCount`.

# Solutions
### Java

```java
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); }
}

```

### CPP

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

```

### Python

```python
class Solution:
    def countBeautifulPairs(self, nums: List[int]) -> int: cnt = [0] * 10 ans = 0 for x in nums: for y in range(10): if cnt[y] and gcd(x % 10, y) == 1: ans += cnt[y] cnt[int(str(x)[0])] += 1 return ans

```