Leetcode 1814: Count Nice Pairs in an Array
You are given an array of non-negative integers. A pair of indices (i, j) is nice if nums[i] + rev(nums[j]) equals nums[j] + rev(nums[i]). Return the number of nice pairs modulo 10^9 + 7.
Problem
Approach
Steps
Complexity
Input: The input consists of an array nums with non-negative integers.
Example: nums = [12, 21, 34, 43]
Constraints:
• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 10^9
Output: Return the number of nice pairs of indices modulo 10^9 + 7.
Example: Output: 2
Constraints:
• The output should be an integer, modulo 10^9 + 7.
Goal: Count the number of nice pairs (i, j) in the array that satisfy the condition nums[i] + rev(nums[j]) = nums[j] + rev(nums[i]).
Steps:
• For each number in the array, calculate the difference between nums[i] and rev(nums[i]).
• Use a hash map to count how many times each difference occurs.
• For each difference count greater than 1, calculate how many pairs of indices can be formed.
• Return the total number of nice pairs modulo 10^9 + 7.
Goal: The input will always meet the constraints listed below.
Steps:
• The length of nums is between 1 and 10^5.
• Each element of nums is between 0 and 10^9.
Assumptions:
• All numbers are non-negative integers.
• The solution must be efficient due to the large input size.
• Input: nums = [12, 21, 34, 43]
• Explanation: In this case, the pairs (0,1) and (2,3) are nice because the sum of each pair and their reversed numbers are equal.
• Input: nums = [5, 100, 100, 500]
• Explanation: The only nice pair is (1,2), where nums[1] + rev(nums[2]) = nums[2] + rev(nums[1]).
Approach: The solution is based on calculating the difference between each number and its reverse, and counting how often each difference appears. This allows us to find how many pairs satisfy the condition.
Observations:
• The problem involves calculating the reverse of each number and comparing differences.
• A brute force solution would be too slow, so an optimized approach using hash maps is necessary.
• By using a hash map to count occurrences of each difference, we can efficiently calculate the number of pairs.
Steps:
• Define a function to reverse the digits of a number.
• For each element in the array, compute the difference between nums[i] and rev(nums[i]).
• Count how many times each difference occurs using a hash map.
• For each difference count greater than 1, calculate the number of nice pairs as (count * (count - 1)) / 2.
• Return the total number of pairs modulo 10^9 + 7.
Empty Inputs:
• The array will not be empty based on the problem constraints.
Large Inputs:
• The algorithm should efficiently handle inputs where nums.length is up to 10^5.
Special Values:
• When nums[i] is 0, rev(0) is also 0.
Constraints:
• The input numbers are always non-negative and between 0 and 10^9.
int countNicePairs(vector<int>& nums) {
unordered_map<int, long> mp;
for(auto &n: nums) mp[n - rev(n)]++;
int mod = 1000000007;
long count = 0;
for(auto &it: mp)
count = (count + (it.second * (it.second - 1))/ 2) % mod;
return count;
}
int rev(int x) {
int revNum = 0;
while(x) revNum = revNum * 10 + (x%10), x /= 10;
return revNum;
}
1 : Function Definition
int countNicePairs(vector<int>& nums) {
This defines the function `countNicePairs` which takes a vector of integers `nums` as input and returns the count of nice pairs.
2 : Map Initialization
unordered_map<int, long> mp;
An unordered map `mp` is initialized to store the frequency of the differences between a number and its reverse.
3 : Frequency Calculation
for(auto &n: nums) mp[n - rev(n)]++;
This loop iterates over each number `n` in the `nums` vector, calculates the difference between `n` and its reversed value, and increments the corresponding frequency in the map `mp`.
4 : Modulo Definition
int mod = 1000000007;
A variable `mod` is defined to store the value of `1000000007`, which is commonly used to avoid overflow in large number calculations.
5 : Count Initialization
long count = 0;
The variable `count` is initialized to 0. This will store the total number of nice pairs.
6 : Count Calculation Loop
for(auto &it: mp)
This loop iterates over each entry in the unordered map `mp`, where `it.second` represents the frequency of a particular difference.
7 : Combination Formula
count = (count + (it.second * (it.second - 1))/ 2) % mod;
This line calculates the number of pairs for the current frequency `it.second` using the combination formula `n * (n - 1) / 2`, and adds it to the total `count`, taking the modulo `mod` to avoid overflow.
8 : Return Statement
return count;
This returns the total number of nice pairs found.
9 : Reversal Function Definition
int rev(int x) {
This defines the helper function `rev` which takes an integer `x` as input and returns its reverse.
10 : Reversal Initialization
int revNum = 0;
A variable `revNum` is initialized to store the reversed number.
11 : Reversal Logic
while(x) revNum = revNum * 10 + (x%10), x /= 10;
This loop reverses the digits of the number `x` by extracting the last digit (x % 10) and adding it to `revNum`, then dividing `x` by 10.
12 : Return Reversed Number
return revNum;
This returns the reversed number `revNum`.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n), where n is the number of elements in the array, as we iterate over the array and perform constant-time operations for each element.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n), where n is the number of elements in the array, as we store the differences in a hash map.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus