Number of beautiful pairs

Array Hash Table Math Counting Number Theory

52.1% acceptance

Feb 25, 2026

236

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_beautiful_pairs(nums: Vec<i32>) -> i32 {
    fn gcd(a: i32, b: i32) -> i32 { if b == 0 { a } else { gcd(b, a % b) } }
    let n = nums.len();
    let mut count = 0;
    for i in 0..n {
      let mut first = nums[i];
      while first >= 10 { first /= 10; }
      for j in i + 1..n {
        let last = nums[j] % 10;
        if gcd(first, last) == 1 { count += 1; }
      }
    }
    count
  }
}