713142. Absolute difference divisible by K
Absolute Difference Divisible by K
713142
Arrays, Hash, Data Structures Goldman Sachs
Summary
Given an array A and an integer K, find all pairs (i, j) such that |A[i] - A[j]| is divisible by K. The problem requires us to find all absolute differences between elements in the array that are multiples of K.
Detailed Explanation
To solve this problem, we can use a hash map to store the frequency of each element's remainder when divided by K. Then, for each element, we can calculate its absolute difference with every other element and check if it is divisible by K. If it is, we add the pair (i, j) to our result set.
Here is the step-by-step breakdown:
- Initialize a hash map
freqto store the frequency of each element's remainder when divided byK. - Iterate through the array and update the frequency of each element's remainder.
- For each element in the array, iterate through the hash map and calculate its absolute difference with every other element whose remainder is the same as the current element.
- Check if the absolute difference is divisible by
K. If it is, add the pair(i, j)to our result set.
The time complexity of this solution is O(n), where n is the size of the array, because we are iterating through the array once and then for each element, we are iterating through the hash map. The space complexity is also O(n) because in the worst case, all elements in the array have different remainders.
Here is a sample ASCII art diagram:
+---------------+
| A[i] - A[j] |
+---------------+
| K |
+---------------+
| remainder |
+---------------+
Optimized Solutions
Java
import java.util.*;
public class Main {
public static List<List<Integer>> findPairs(int[] A, int K) {
Map<Integer, Integer> freq = new HashMap<>();
List<List<Integer>> result = new ArrayList<>();
for (int num : A) {
int remainder = num % K;
freq.put(remainder, freq.getOrDefault(remainder, 0) + 1);
}
for (int i = 0; i < A.length; i++) {
for (int j = i + 1; j < A.length; j++) {
int diff = Math.abs(A[i] - A[j]);
if (diff % K == 0) {
result.add(Arrays.asList(i, j));
}
}
}
return result;
}
}