LeetCode 2748: Number of Beautiful Pairs Solution

Master LeetCode problem 2748 (Number of Beautiful Pairs), a easy challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2748. Number of Beautiful Pairs

Easy

Array Hash Table Math Counting Number Theory

Problem Explanation

Explanation:

To solve this problem, we can iterate over all pairs of indices (i, j) where 0 <= i < j < nums.length, and check if the first digit of nums[i] and the last digit of nums[j] are coprime. We can use a helper function to check if two numbers are coprime by calculating their greatest common divisor (GCD) and checking if it equals 1.

Algorithm:
1. Initialize a counter beautifulPairs to 0.
2. Iterate over all pairs of indices (i, j) where 0 <= i < j < nums.length.
3. Check if the first digit of nums[i] and the last digit of nums[j] are coprime using a helper function.
4. If they are coprime, increment beautifulPairs.
5. Return the beautifulPairs count.
Time Complexity: O(n^2) where n is the length of the input array nums.
Space Complexity: O(1) as we are using constant extra space.

Solution Code

class Solution {
    public int countBeautifulPairs(int[] nums) {
        int beautifulPairs = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (areCoprime(nums[i], nums[j])) {
                    beautifulPairs++;
                }
            }
        }
        return beautifulPairs;
    }

    private boolean areCoprime(int a, int b) {
        return gcd(a, b) == 1;
    }

    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2748 (Number of Beautiful Pairs)?

This page provides optimized solutions for LeetCode problem 2748 (Number of Beautiful Pairs) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2748 (Number of Beautiful Pairs)?

The time complexity for LeetCode 2748 (Number of Beautiful Pairs) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2748 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2748 in Java, C++, or Python.

Back to LeetCode Solutions