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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Beautiful Pairs

Number: 2831

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

Given an integer array nums, count the number of beautiful pairs (i, j) where 0 <= i < j < nums.length such that the first digit of nums[i] and the last digit of nums[j] are coprime. Two integers are coprime if their greatest common divisor (gcd) is 1.

Key Insights

  • The input size is small (nums.length between 2 and 100), so an O(n²) solution is acceptable.
  • Extracting the first digit of a number can be done by repeatedly dividing by 10 (or converting to a string).
  • The last digit of a number is simply nums[j] % 10.
  • Use gcd to check if two numbers are coprime.
  • Iterate through all pairs with i < j, compute the required digits, and count the pair if they are coprime.

Space and Time Complexity

Time Complexity: O(n²) – since we examine every pair of indices. Space Complexity: O(1) – only constant extra space is used.

Solution

We loop through the array with two indices (i and j) ensuring i < j. For each pair, we extract: • The first digit of nums[i] by repeatedly dividing by 10 until the number is less than 10. • The last digit of nums[j] using modulo operation (nums[j] % 10). Then, we calculate the gcd of these two digits. If the gcd is 1, the digits are coprime and we increment our count. This straightforward approach leverages basic arithmetic operations and the math gcd function.

Code Solutions

# Import the math module for gcd function
import math

def beautifulPairs(nums):
    count = 0  # Initialize counter for beautiful pairs
    
    # Helper function to get the first digit of a number
    def get_first_digit(num):
        while num >= 10:  # Loop until the number is a single digit
            num //= 10
        return num

    n = len(nums)
    # Iterate over all pairs (i, j) with i < j
    for i in range(n):
        first_digit = get_first_digit(nums[i])  # Get first digit of nums[i]
        for j in range(i + 1, n):
            last_digit = nums[j] % 10  # Get last digit of nums[j]
            # Check if the first and last digits are coprime using gcd
            if math.gcd(first_digit, last_digit) == 1:
                count += 1  # Increment count if they are coprime
    return count

# Example usage:
print(beautifulPairs([2, 5, 1, 4]))  # Expected output: 5
← Back to All Questions