algoadvance

Leetcode 2748. Number of Beautiful Pairs

Problem Statement

Given an array of positive integers nums, a pair (i, j) is called beautiful if 1 <= i < j <= nums.length and the greatest common divisor (GCD) of the first digit of nums[i] and the last digit of nums[j] is 1. Return the number of beautiful pairs in the array nums.

Clarifying Questions

1. Input Constraints:
   • What is the maximum length of the array nums?
   • What are the possible ranges for the values within nums?
2. Output Requirements:
   • Should the output be the total count of beautiful pairs, or additionally, should we return the pairs themselves?
3. Edge Cases:
   • What should be returned if nums contains only one element?

Strategy

1. Extract Digits:
   • For each number in nums, extract the first and the last digits.
2. Check GCD Condition:
   • Use the __gcd function from the <numeric> library to check if the GCD of the first digit of nums[i] and the last digit of nums[j] is 1.
3. Counting Pairs:
   • Iterate over all pairs (i, j) where 1 <= i < j <= nums.length and count those pairs which meet the condition.

Code

#include <iostream>
#include <vector>
#include <numeric>  // for __gcd function

int firstDigit(int num) {
    while (num >= 10) {
        num /= 10;
    }
    return num;
}

int lastDigit(int num) {
    return num % 10;
}

int countBeautifulPairs(const std::vector<int>& nums) {
    int n = nums.size();
    int beautifulPairsCount = 0;
    
    for (int i = 0; i < n; ++i) {
        int firstDigitI = firstDigit(nums[i]);
        for (int j = i + 1; j < n; ++j) {
            int lastDigitJ = lastDigit(nums[j]);
            if (std::gcd(firstDigitI, lastDigitJ) == 1) {
                beautifulPairsCount++;
            }
        }
    }
    
    return beautifulPairsCount;
}

int main() {
    std::vector<int> nums = {13, 25, 32, 49};
    std::cout << "Number of beautiful pairs: " << countBeautifulPairs(nums) << std::endl;
    return 0;
}

Time Complexity

• Extraction of digits: Each number requires a logarithmic time operation to extract the first digit which can be approximated as (O(1)) since the numbers are bounded.
• Nested loop: The loops to generate pairs (i, j) have a time complexity of (O(n^2)).
• GCD Calculation: Each GCD computation is (O(\log(\min(a, b)))), but since the digits involved are only from 1 to 9, this is also (O(1)).

Hence, the overall time complexity is (O(n^2)) where (n) is the length of nums.

Space Complexity

• The space used is constant (O(1)) beyond the input data because we only store a few integer variables.

This solution efficiently and clearly identifies the number of beautiful pairs by leveraging straightforward algorithm constructs and the properties of GCD.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• 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?