We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Number of Beautiful Pairs

Difficulty: Easy

Problem Description

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 gcd(x, y) == 1.

Key Insights

  • The problem requires determining pairs of indices based on the first digit of one number and the last digit of another.
  • The first digit of a number can be obtained by converting it to a string and taking the first character.
  • The last digit can be easily obtained using the modulus operator.
  • The GCD (Greatest Common Divisor) function can be utilized to determine if two numbers are coprime.
  • The complexity is manageable due to the constraints, allowing for a nested loop solution.

Space and Time Complexity

Time Complexity: O(n^2)
Space Complexity: O(1)

Solution

To solve the problem, we will use a nested loop where the outer loop iterates through the first element (i) and the inner loop iterates through the second element (j). We will extract the first digit of nums[i] and the last digit of nums[j], then check if they are coprime using the GCD function. If they are coprime, we will increment our count of beautiful pairs. This approach efficiently counts the pairs within the given constraints.

Code Solutions

def gcd(x, y):
    while y:
        x, y = y, x % y
    return x

def countBeautifulPairs(nums):
    count = 0
    n = len(nums)
    
    for i in range(n):
        first_digit = int(str(nums[i])[0])  # Get the first digit
        for j in range(i + 1, n):
            last_digit = nums[j] % 10  # Get the last digit
            if gcd(first_digit, last_digit) == 1:  # Check if they are coprime
                count += 1
    return count
← Back to All Questions