Check If Array Pairs Are Divisible by k solution and explanation
Google
TCS
9 more videos on this problem
Leetcode 1497. Check If Array Pairs Are Divisible by kFraz · 13:46 · 19K views
Check If Array Pairs Are Divisible by k | Simplest Explanation | Leetcode 1497 | codestorywithMIKcodestorywithMIK · 24:00 · 15K views
Check If Array Pairs Are Divisible by k | Leetcode 1497Techdose · 12:53 · 7K views
1497. Check If Array Pairs Are Divisible by k | maths | hash | Leetcode Daily Challenge | DSA | JavaShashCode · 12:58 · 4K views
Daily Leetcode #1645: Oct 01, 2024 - 1497. Check If Array Pairs Are Divisible by kProgramming Live with Larry · 10:05 · 1K views
1497. Check If Array Pairs Are Divisible by k (Leetcode Medium)Programming Live with Larry · 3:57 · 1K views
Leetcode 1497 Check If Array Pairs Are Divisible by kJeevan Kumar - Cracckify · 6:21 · 688 views
1497. Check If Array Pairs Are Divisible by k | JSer - JavaScript & AlgorithmJSer · 16:22 · 418 views
Leetcode 1497 Check If Array Pairs Are Divisible by kMath Geeks · 4:28 · 253 views
LeetCode 1497 - Check If Array Pairs Are Divisible by k - JavaAlpha-Code · 14:22 · 214 views
The problem
Given an array of integers arr of even length n and an integer k.
We want to divide the array into exactly n / 2 pairs such that the sum of each pair is divisible by k.
Return true If you can find a way to do that or false otherwise.
Example 1:
Input: arr = [1,2,3,4,5,10,6,7,8,9], k = 5 Output: true Explanation: Pairs are (1,9),(2,8),(3,7),(4,6) and (5,10).
Example 2:
Input: arr = [1,2,3,4,5,6], k = 7 Output: true Explanation: Pairs are (1,6),(2,5) and(3,4).
Example 3:
Input: arr = [1,2,3,4,5,6], k = 10 Output: false Explanation: You can try all possible pairs to see that there is no way to divide arr into 3 pairs each with sum divisible by 10.
Constraints:
arr.length == n1 <= n <= 105nis even.-109 <= arr[i] <= 1091 <= k <= 105
Approach overview
Problem Overview: You receive an integer array and a value k. The task is to determine whether the array can be partitioned into pairs such that the sum of every pair is divisible by k. Each element must be used exactly once, so the challenge is verifying that every value finds a compatible partner.
Approach 1: Sorting and Two-Pointer Technique (O(n log n) time, O(1) extra space)
This approach starts by sorting the array so values with similar remainders cluster together. After sorting, compute each element’s remainder with k and use two pointers from opposite ends to attempt forming valid pairs. For any pair (a, b), check if (a + b) % k == 0. Sorting enables structured traversal while two pointers progressively match candidates from both ends of the array.
This method works best when the array is already sorted or when you want a deterministic pairing process without additional memory. The downside is the O(n log n) sorting cost. It also requires careful pointer adjustments when sums fail the divisibility condition. The technique mainly relies on array traversal patterns and controlled pointer movement.
Approach 2: Utilize Hashing for Faster Look-up (O(n) time, O(k) space)
The key observation: if two numbers form a valid pair, their remainders must complement each other. For a number with remainder r, its partner must have remainder (k - r) % k. Iterate through the array and compute num % k. Maintain a frequency map that counts how many times each remainder appears.
After counting, validate the pairing rules. Remainder 0 values must occur an even number of times because they can only pair with each other. For any other remainder r, the count of r must equal the count of k - r. This guarantees every element finds a valid complement whose sum is divisible by k.
This method relies on a hash table to track remainder frequencies and simple arithmetic to verify complements. Because each element is processed once, the total time complexity stays O(n) with O(k) extra space for remainder counts. It’s a classic use of modular arithmetic and counting techniques.
Recommended for interviews: The hashing approach is the expected solution. Interviewers want to see the remainder complement insight and the ability to translate it into a frequency map check. The sorting approach demonstrates problem exploration, but the O(n) hash-based method shows stronger algorithmic reasoning and is typically preferred in coding interviews.
Approach 1: Approach 1: Use Sorting and Two-Pointer Technique
The problem can be approached by first sorting the data of interest and then using the two-pointer technique to solve it efficiently. This method leverages the sorted nature of the data to reduce the complexity of finding comparisons or sums. The two-pointer technique usually involves placing two pointers at different positions in the array and moving them according to the condition checks on the sum or comparison of their pointed values. This allows for efficient traversal with lesser computations.
#include <iostream>
#include <vector>
#include <algorithm>
void solve(std::vector<int>& arr) {
std::sort(arr.begin(), arr.end());
int left = 0, right = arr.size() - 1;
while (left < right) {
int sum = arr[left] + arr[right];
if (sum == 0) {
std::cout << "Pair found: " << arr[left] << ", " << arr[right] << std::endl;
return;
} else if (sum < 0) {
++left;
} else {
--right;
}
}
std::cout << "No pair found" << std::endl;
}
int main() {
std::vector<int> arr = {-1, 2, -3, 4, 5, -6};
solve(arr);
return 0;
}#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
void solve(int* arr, int n) {
qsort(arr, n, sizeof(int), compare);
int left = 0, right = n - 1;
while (left < right) {
int sum = arr[left] + arr[right];
if (sum == 0) {
printf("Pair found: %d, %d\n", arr[left], arr[right]);
return;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
printf("No pair found\n");
}
int main() {
int arr[] = {-1, 2, -3, 4, 5, -6};
int n = sizeof(arr) / sizeof(arr[0]);
solve(arr, n);
return 0;
}In this C++ implementation, we use STL to sort the array and proceed with the two-pointer technique. Each iteration checks the sum of the smallest and largest element and adjusts pointers based on the sum in relation to the target (0 in this case).
Time Complexity: O(n log n) due to sorting, followed by O(n) operations in the two-pointer search. Overall: O(n log n).
Space Complexity: O(1) as it uses in-place modifications.
Approach 2: Approach 2: Utilize Hashing for Faster Look-up
An efficient alternative to sorting could be the usage of a hash table (or unordered map) that enables O(1) average-time complexity for search operations. By inserting each element into the hash table and checking if the complementary value (to make a sum zero) exists, one can get the desired pair in linear time without needing to sort the entire array.
def solve(arr):
hash_map = {}
for num in arr:
if -num in hash_map:
print(f"Pair found: {num}, {-num}")
return
hash_map[num] = True
print("No pair found")
arr = [-1, 2, -3, 4, 5, -6]
solve(arr)import java.util.HashMap;
public class Main {
public static void solve(int[] arr) {
HashMap<Integer, Boolean> hashMap = new HashMap<>();
for (int num : arr) {
if (hashMap.containsKey(-num)) {
System.out.println("Pair found: " + num + ", " + (-num));
return;
}
hashMap.put(num, true);
}
System.out.println("No pair found");
}
public static void main(String[] args) {
int[] arr = {-1, 2, -3, 4, 5, -6};
solve(arr);
}
}This Python solution uses a dictionary to store elements. It then checks for each element if its negation exists in the dictionary. If a complement is found, a solution is printed, otherwise the iteration continues until all elements are processed.
Time Complexity: O(n) on average for insertion and look-up.
Space Complexity: O(n) due to storage in the hash map.
Approach 3: Counting Remainders
The sum of two numbers a and b is divisible by k if and only if the sum of their remainders when divided by k is divisible by k.
Therefore, we can count the remainder of each number in the array when divided by k, and record them in an array cnt. Then we traverse the array cnt. For each number i in the range [1,..k-1], if the values of cnt[i] and cnt[k-i] are not equal, it means we cannot divide the numbers in the array into n/2 pairs such that the sum of each pair is divisible by k. Similarly, if the value of cnt[0] is not even, it also means we cannot divide the numbers in the array into n/2 pairs such that the sum of each pair is divisible by k.
The time complexity is O(n), where n is the length of the array arr. The space complexity is O(k).
/**
* @param {number[]} arr
* @param {number} k
* @return {boolean}
*/
var canArrange = function (arr, k) {
const cnt = Array(k).fill(0);
for (const x of arr) {
++cnt[((x % k) + k) % k];
}
for (let i = 1; i < k; ++i) {
if (cnt[i] !== cnt[k - i]) {
return false;
}
}
return cnt[0] % 2 === 0;
};function canArrange(arr: number[], k: number): boolean {
const cnt: number[] = Array(k).fill(0);
for (const x of arr) {
++cnt[((x % k) + k) % k];
}
for (let i = 1; i < k; ++i) {
if (cnt[i] !== cnt[k - i]) {
return false;
}
}
return cnt[0] % 2 === 0;
}func canArrange(arr []int, k int) bool {
cnt := make([]int, k)
for _, x := range arr {
cnt[(x%k+k)%k]++
}
for i := 1; i < k; i++ {
if cnt[i] != cnt[k-i] {
return false
}
}
return cnt[0]%2 == 0
}impl Solution {
pub fn can_arrange(arr: Vec<i32>, k: i32) -> bool {
let k = k as usize;
let mut cnt = vec![0; k];
for &x in &arr {
cnt[((x % k as i32 + k as i32) % k as i32) as usize] += 1;
}
for i in 1..k {
if cnt[i] != cnt[k - i] {
return false;
}
}
cnt[0] % 2 == 0
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Use Sorting and Two-Pointer Technique | Time Complexity: O(n log n) due to sorting, followed by O(n) operations in the two-pointer search. Overall: O(n log n). |
| Approach 2: Utilize Hashing for Faster Look-up | Time Complexity: O(n) on average for insertion and look-up. |
| Counting Remainders | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting + Two Pointers | O(n log n) | O(1) | When avoiding extra memory or when the array is already sorted |
| Hash Map Remainder Counting | O(n) | O(k) | General case and interview-preferred optimal solution |
Frequently asked questions
Is Check If Array Pairs Are Divisible by k easy or hard?
The problem is rated Medium on LeetCode. The implementation is straightforward once you recognize the remainder complement rule, but identifying that modular arithmetic insight is what makes it a typical medium-level interview question.
Check If Array Pairs Are Divisible by k Python/Java solution
Python and Java solutions typically use a dictionary or HashMap to track remainder frequencies. After counting remainders, iterate through the map to ensure every remainder r has a matching k - r frequency and handle special cases like remainder 0.
How to solve Check If Array Pairs Are Divisible by k in O(n)?
Compute num % k for every element and store frequencies in a hash map or array. For each remainder r, ensure its frequency matches the frequency of k - r. Handle edge cases where r = 0 (must be even count) and when r = k/2 if k is even. This single pass plus validation gives an O(n) solution.
What is the best approach for Check If Array Pairs Are Divisible by k?
The best approach uses hashing with remainder counting. Compute each element's remainder modulo k and store frequencies in a hash map. For a valid pairing, the count of remainder r must equal the count of k - r, and remainder 0 values must appear an even number of times. This approach runs in O(n) time with O(k) space.
Is Check If Array Pairs Are Divisible by k asked at Google/Amazon/Meta?
Variants of remainder pairing and modular arithmetic problems appear in interviews at companies like Amazon and Google. These companies often test hash map reasoning, complement matching, and array frequency techniques similar to this problem.
What data structure is used in Check If Array Pairs Are Divisible by k?
A hash table (or frequency array) stores counts of each remainder when elements are divided by k. This structure enables constant-time lookup to verify that each remainder has a matching complementary remainder.
What is the time complexity of Check If Array Pairs Are Divisible by k?
The optimal solution runs in O(n) time by scanning the array once and counting remainders in a hash map. Validation of remainder pairs takes O(k). The space complexity is O(k) because at most k remainder values are stored.