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 <stdio.h>
2#
This C implementation uses two nested loops to check each pair of indices. It calculates the reverse of both numbers and compares their sum to find nice pairs.
It's a straightforward approach that leverages direct pairwise comparison, but this results in less efficiency for large inputs. Suitable for educational purposes or small arrays, it helps grasp the mechanics without advanced data structures.