algoadvance

Given an array of positive integers nums, return the number of beautiful pairs in the array. A beautiful pair is defined as follows:

• A pair of indices (i, j) (where i < j) such that the greatest common divisor (GCD) of the first digit of nums[i] and the last digit of nums[j] is 1.

Example:

• Input: nums = [12, 34, 56, 78]
• Output: 3

In the example above, the beautiful pairs are (0, 1), (0, 2), and (0, 3) because the GCD of the first digit of nums[0], nums[1], and nums[2] with the last digit of nums[1], nums[2], and nums[3] respectively all equal 1.

Clarifying Questions

1. Q: Can nums contain only one element? A: No, nums should contain at least two elements for pairs to exist.

2. Q: Are the numbers in nums guaranteed to be positive integers? A: Yes, the numbers in nums are positive integers.

3. Q: What is the range of the numbers in nums? A: The problem does not specify, but we can assume they fit within the typical constraints of an integer in competitive programming settings (e.g., 32-bit integers).

Strategy

1. Extract Digits:
   • Compute the first digit of nums[i] by repeatedly dividing by 10 until the number is a single digit.
   • Compute the last digit of nums[j] using the modulus operation (nums[j] % 10).
2. Check Pairing Condition:
   • For each combination of indices (i, j) where i < j, check if the GCD of the first digit of nums[i] and the last digit of nums[j] equals 1.
3. Count Pairs:
   • Maintain a count of how many such pairs exist that satisfy the above condition.
4. Efficiency Consideration:
   • Since the calculation involves pairs, the complexity is O(n^2) in the worst case (where n is the length of nums). This might be acceptable for reasonably small values of n.

Code

import math

def countBeautifulPairs(nums):
    def get_first_digit(n):
        while n >= 10:
            n //= 10
        return n
    
    count = 0
    n = len(nums)
    
    for i in range(n):
        first_digit = get_first_digit(nums[i])
        for j in range(i + 1, n):
            last_digit = nums[j] % 10
            if math.gcd(first_digit, last_digit) == 1:
                count += 1
                
    return count

# Example usage:
nums = [12, 34, 56, 78]
print(countBeautifulPairs(nums))  # Output should be 3

Time Complexity

• Time Complexity: O(n^2)
  • We are iterating through all pairs (i, j) with i < j, hence the nested loop results in O(n^2).
  • Computation of the first and last digits and GCD are considered O(log10(num)) which is insignificant compared to O(n^2) complexity of the nested iteration.
• Space Complexity: O(1)
  • We are using a constant amount of additional space regardless of the input size.

This code ensures that we accurately count all beautiful pairs in the given list nums according to the specified criteria.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?