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 innums.

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.

Examples

Example 1

1
2
3
4
5
6
7
8
9

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

1
2
3
4
5
6

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

Solution

Method 1 – Brute Force with Digit Extraction

Intuition

For each pair (i, j) with i < j, extract the first digit of nums[i] and last digit of nums[j], check if they are coprime.

Approach

  1. For each i < j, extract first digit of nums[i] and last digit of nums[j].
  2. Check gcd(first, last) == 1.
  3. Count and return total pairs.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

#include <vector>
using namespace std;
class Solution {
public:
    int beautifulPairs(vector<int>& nums) {
        int n = nums.size(), ans = 0;
        auto first = [](int x) { while (x >= 10) x /= 10; return x; };
        auto last = [](int x) { return x % 10; };
        auto gcd = [](int a, int b) { while (b) { int t = b; b = a % b; a = t; } return a; };
        for (int i = 0; i < n; ++i)
            for (int j = i+1; j < n; ++j)
                if (gcd(first(nums[i]), last(nums[j])) == 1) ++ans;
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func beautifulPairs(nums []int) int {
    n := len(nums); ans := 0
    first := func(x int) int { for x >= 10 { x /= 10 }; return x }
    last := func(x int) int { return x % 10 }
    gcd := func(a, b int) int { for b != 0 { a, b = b, a%b }; return a }
    for i := 0; i < n; i++ {
        for j := i+1; j < n; j++ {
            if gcd(first(nums[i]), last(nums[j])) == 1 { ans++ }
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    public int beautifulPairs(int[] nums) {
        int n = nums.length, ans = 0;
        for (int i = 0; i < n; ++i)
            for (int j = i+1; j < n; ++j)
                if (gcd(first(nums[i]), last(nums[j])) == 1) ans++;
        return ans;
    }
    int first(int x) { while (x >= 10) x /= 10; return x; }
    int last(int x) { return x % 10; }
    int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    fun beautifulPairs(nums: IntArray): Int {
        fun first(x: Int) = generateSequence(x) { it/10 }.first { it < 10 }
        fun last(x: Int) = x % 10
        fun gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
        var ans = 0
        for (i in nums.indices)
            for (j in i+1 until nums.size)
                if (gcd(first(nums[i]), last(nums[j])) == 1) ans++
        return ans
    }
}
1
2
3
4
5
6
7
8

from math import gcd
class Solution:
    def beautifulPairs(self, nums: List[int]) -> int:
        def first(x):
            while x >= 10: x //= 10
            return x
        def last(x): return x % 10
        return sum(gcd(first(nums[i]), last(nums[j])) == 1 for i in range(len(nums)) for j in range(i+1, len(nums)))
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

impl Solution {
    pub fn beautiful_pairs(nums: Vec<i32>) -> i32 {
        fn first(x: i32) -> i32 { let mut x = x; while x >= 10 { x /= 10; } x }
        fn last(x: i32) -> i32 { x % 10 }
        fn gcd(a: i32, b: i32) -> i32 { if b == 0 { a } else { gcd(b, a % b) } }
        let n = nums.len(); let mut ans = 0;
        for i in 0..n {
            for j in i+1..n {
                if gcd(first(nums[i]), last(nums[j])) == 1 { ans += 1; }
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

function beautifulPairs(nums: number[]): number {
    const first = (x: number) => { while (x >= 10) x = Math.floor(x/10); return x; };
    const last = (x: number) => x % 10;
    const gcd = (a: number, b: number): number => b === 0 ? a : gcd(b, a % b);
    let ans = 0;
    for (let i = 0; i < nums.length; ++i)
        for (let j = i+1; j < nums.length; ++j)
            if (gcd(first(nums[i]), last(nums[j])) === 1) ans++;
    return ans;
}

Complexity

  • ⏰ Time complexity: O(n^2)
  • 🧺 Space complexity: O(1)