Leetcode 2748: Number of Beautiful Pairs
You are given an array ’nums’ containing integers. A pair of indices ‘i, j’ is considered beautiful if the first digit of nums[i] and the last digit of nums[j] are coprime. Two numbers are coprime if their greatest common divisor (GCD) is 1, i.e., ‘gcd(x, y) == 1’. Your task is to find the total number of beautiful pairs in nums.
Problem
Approach
Steps
Complexity
Input: You will be given an array of integers 'nums'. Each element in 'nums' is an integer with 1 to 4 digits.
Example: nums = [4, 15, 33, 17]
Constraints:
• 2 <= nums.length <= 100
• 1 <= nums[i] <= 9999
• nums[i] % 10 != 0
Output: Return the total number of beautiful pairs in the given array.
Example: For nums = [4, 15, 33, 17], the output is 6.
Constraints:
• The output is an integer representing the number of beautiful pairs.
Goal: Identify all pairs i, j such that the first digit of nums[i] and the last digit of nums[j] are coprime.
Steps:
• Iterate over all possible pairs of indices i, j where i < j.
• Extract the first digit of nums[i] and the last digit of nums[j].
• Check if the GCD of the first digit and last digit is 1 using the 'gcd' function.
• Count the pairs where GCD is 1.
Goal: Ensure that nums has at least 2 elements and each element in nums is between 1 and 9999, and its last digit is not 0.
Steps:
• 2 <= nums.length <= 100
• 1 <= nums[i] <= 9999
• nums[i] % 10 != 0
Assumptions:
• The input will always contain valid integers in the range 1 to 9999.
• Input: For nums = [4, 15, 33, 17]
• Explanation: You need to check every possible pair (i, j) where i < j and verify if the first digit of nums[i] and the last digit of nums[j] are coprime. The GCD of these digits should be 1.
Approach: We use a brute force approach to check every possible pair of indices in the array. For each pair, we extract the first digit of the first number and the last digit of the second number, and check if their GCD is 1.
Observations:
• The task requires checking pairs of digits, which is computationally feasible with a brute-force approach.
• Since the array length is limited to 100, checking all pairs is manageable.
Steps:
• Iterate over each pair of indices i, j where i < j.
• For each pair, extract the first digit of nums[i] and the last digit of nums[j].
• Use the gcd function to check if the digits are coprime.
• Count the pairs that satisfy the condition.
Empty Inputs:
• The input will always contain at least 2 elements, so this case won't occur.
Large Inputs:
• If nums has 100 elements, the brute-force approach will check at most 4950 pairs, which is feasible within the given constraints.
Special Values:
• The last digit of any number in nums will never be 0, ensuring valid inputs for checking GCD.
Constraints:
• Ensure that nums[i] does not end with a zero.
int countBeautifulPairs(vector<int>& nums) {
int cnt[10] = {}, res = 0;
for(int i = 0; i < nums.size(); ++i) {
for (int n = 1; n < 10; ++n)
if (gcd(n, nums[i] % 10) == 1)
res += cnt[n];
while (nums[i] >= 10)
nums[i] /= 10;
++cnt[nums[i]];
}
return res;
}
1 : Function Definition
int countBeautifulPairs(vector<int>& nums) {
Defines the function `countBeautifulPairs`, which takes a vector `nums` containing integers and returns an integer representing the count of 'beautiful' pairs.
2 : Variable Initialization
int cnt[10] = {}, res = 0;
Initializes an array `cnt` of size 10 to count occurrences of digits (last digits of numbers) and a variable `res` to store the result (the number of beautiful pairs).
3 : Outer Loop
for(int i = 0; i < nums.size(); ++i) {
Iterates over each element in the `nums` array to process each number.
4 : Inner Loop
for (int n = 1; n < 10; ++n)
For each number in `nums`, this loop iterates through numbers `n` from 1 to 9 and checks the greatest common divisor (gcd) with the last digit of the current number.
5 : GCD Condition
if (gcd(n, nums[i] % 10) == 1)
Checks if the gcd of `n` and the last digit of `nums[i]` is 1, meaning that the pair (last digit of `nums[i]`, `n`) is 'beautiful.'
6 : Increment Result
res += cnt[n];
If the gcd condition is satisfied, the result `res` is incremented by the count of previous numbers in `nums` whose last digit is `n`.
7 : While Loop for Last Digit Extraction
while (nums[i] >= 10)
This while loop reduces the current number `nums[i]` by removing its last digit repeatedly until it becomes a single-digit number.
8 : Last Digit Removal
nums[i] /= 10;
Divides `nums[i]` by 10 to remove its last digit.
9 : Update Count
++cnt[nums[i]];
Increments the count of occurrences for the last digit of the current number `nums[i]` in the `cnt` array.
10 : Return Statement
return res;
Returns the final result `res`, which represents the number of beautiful pairs found in the `nums` array.
Best Case: O(n^2) where n is the length of nums.
Average Case: O(n^2).
Worst Case: O(n^2).
Description: We check each pair of indices (i, j), which leads to O(n^2) time complexity.
Best Case: O(1).
Worst Case: O(1).
Description: We only use a few variables to store intermediate results, so the space complexity is constant.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus