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.
1import java.util.HashMap;
2
3public class CountNicePairs {
4 public int countNicePairs(int[] nums) {
5 final int MOD = 1000000007;
6 HashMap<Integer, Integer> countMap = new HashMap<>();
7 int result = 0;
8
9 for (int num : nums) {
10 int diff = num - reverse(num);
11 int count = countMap.getOrDefault(diff, 0);
12 result = (result + count) % MOD;
13 countMap.put(diff, count + 1);
14 }
15
16 return result;
17 }
18
19 private int reverse(int num) {
20 int reversed = 0;
21 while (num > 0) {
22 reversed = reversed * 10 + num % 10;
23 num /= 10;
24 }
25 return reversed;
26 }
27
28 public static void main(String[] args) {
29 CountNicePairs solution = new CountNicePairs();
30 int[] nums = {42, 11, 1, 97};
31 System.out.println(solution.countNicePairs(nums)); // Output: 2
32 }
33}This solution uses a HashMap to store the frequencies of computed differences to optimize the counting of nice pairs.
For each element in the nums array, we compute its difference with its reverse. We then use a HashMap to keep track of numbers we've seen, allowing us to compute the number of nice pairs in constant time per element.
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.