Sponsored
Sponsored
For a nice pair, nums[i] + rev(nums[j]) = nums[j] + rev(nums[i]) implies nums[i] - rev(nums[i]) = nums[j] - rev(nums[j]). Use this invariant property to compute measurable differences for each index.
Transform each element nums[i] in the array to nums[i] - rev(nums[i]). Count the frequency of each difference to compute the number of pairs (i, j) with this characteristic efficiently.
Time Complexity: O(N), where N is the length of the nums array since we process each number in the array in constant time.
Space Complexity: O(N), for storing the frequencies of differences.
1def countNicePairs(nums):
2 MOD = 10**9 + 7
3 def reverse(x):
4 return int(str(x)[::-1])
5
6 count = {}
7 res = 0
8
9 for num in nums:
10 difference = num - reverse(num)
11 if difference in count:
12 res = (res + count[difference]) % MOD
13 count[difference] += 1
14 else:
15 count[difference] = 1
16
17 return res
18
19nums = [42,11,1,97]
20print(countNicePairs(nums)) # Output: 2The solution builds on the idea that the equation nums[i] - rev(nums[i]) == nums[j] - rev(nums[j]) describes a relationship that clearly defines a valid condition for 'nice' index pairs.
Every time a particular difference is encountered, we count how many times it has appeared previously to compute how many pairs can be formed based on past occurrences, thus avoiding a direct double loop and optimizing for time complexity.
Another less efficient, but intuitive approach is to use a two-pointer technique to check each pair (i, j) for the nice pair condition. This approach isn't time optimized for large input sizes but serves to clearly enforce the criteria pairwise and verify the conditions directly.
This method involves going through each pair directly to see if the condition holds. Although easy to think about, it is not suitable for large-sized arrays.
Time Complexity: O(N²), where N is the size of the array, due to the pairwise comparison.
Space Complexity: O(1), constant space as no additional data structures are used.
1#include <iostream>
2#include <vector>
3
4int reverse(int num) {
int reversed = 0;
while (num > 0) {
reversed = reversed * 10 + num % 10;
num /= 10;
}
return reversed;
}
int countNicePairs(std::vector<int>& nums) {
int MOD = 1000000007;
int size = nums.size();
long result = 0;
for (int i = 0; i < size; ++i) {
for (int j = i + 1; j < size; ++j) {
if (nums[i] + reverse(nums[j]) == nums[j] + reverse(nums[i])) {
result = (result + 1) % MOD;
}
}
}
return static_cast<int>(result);
}
int main() {
std::vector<int> nums = {42, 11, 1, 97};
std::cout << countNicePairs(nums) << std::endl; // Output: 2
return 0;
}This C++ code performs a simple pairwise comparison using two nested loops. It calculates the reverse of each number and checks if the condition for forming a nice pair is satisfied.
While conceptually simple, this technique serves as an implementation focused on stepping through logic, as it clearly verifies each condition, albeit inefficiently for large datasets.