Check If Array Pairs Are Divisible by k

Med

#1381Time: O(n + k). We iterate through the input array of size `n` once to build the frequency map, and then we iterate through the frequency array of size `k` (or `k/2`) once to check the conditions.Space: O(k), as we need an auxiliary array of size `k` to store the frequencies of the remainders.2 companies

Patterns

Counting

Data structures

Array Hash Table

Companies

Visa DevRev

Prompt

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 == n
1 <= n <= 10⁵
n is even.
-10⁹ <= arr[i] <= 10⁹
1 <= k <= 10⁵

Approaches

2 approaches with complexity analysis and trade-offs.

A much more efficient and optimal approach leverages modular arithmetic. The key insight is that for a pair (a, b) to have a sum divisible by k, their remainders must complement each other. That is, (a % k + b % k) % k == 0. This implies that for an element with remainder r, its partner must have a remainder of k - r (or 0 if r is 0). Instead of trying to pair actual numbers, we can just count the frequencies of their remainders and check if these counts allow for a valid pairing.

Algorithm

Create an integer array remainderCounts of size k, initialized to all zeros. This array will store the frequency of each possible remainder.
Iterate through each number num in the input array arr.
For each num, calculate its remainder modulo k. To handle negative numbers correctly and ensure the remainder is in the range [0, k-1], use the formula rem = ((num % k) + k) % k.
Increment the count for this remainder: remainderCounts[rem]++.
After populating the frequency array, check the pairing conditions:
- Check remainderCounts[0]. Since elements with a remainder of 0 can only be paired with other elements with a remainder of 0, their total count must be even. If remainderCounts[0] % 2 != 0, return false.
- Iterate from r = 1 up to k / 2.
- For each r, if r * 2 == k (which only happens if k is even and r = k/2), these elements must pair with each other. Thus, remainderCounts[r] must be even. If not, return false.
- Otherwise (if r != k-r), an element with remainder r must pair with an element with remainder k-r. Therefore, their counts must be equal. If remainderCounts[r] != remainderCounts[k - r], return false.
If all conditions are met after checking all remainders, it means a valid pairing is possible. Return true.

Walkthrough

This method transforms the problem from pairing numbers to pairing remainders. We don't care about the numbers themselves, only their remainders when divided by k.

The algorithm proceeds in two main phases:

Counting Remainders: We iterate through the entire input array arr once. For each number, we compute its remainder modulo k. A crucial detail is handling potentially negative numbers in arr. The standard % operator in Java can yield negative results (e.g., -1 % 5 is -1). To map all remainders to the non-negative range [0, k-1], we use the expression ((num % k) + k) % k. We use an array of size k to store the frequency of each of these non-negative remainders.
Verifying Frequencies: After counting, we check if the frequencies allow for perfect pairing.
- Remainder 0: An element x with x % k == 0 needs a partner y with y % k == 0. This means all elements divisible by k must be paired amongst themselves. Therefore, the total count of such elements (remainderCounts[0]) must be even.
- Complementary Remainders: An element x with remainder r (where r != 0) needs a partner y with remainder k - r. This means the number of elements with remainder r must exactly match the number of elements with remainder k - r.
- Special Case r = k/2: If k is an even number, a special case arises for the remainder r = k / 2. Here, k - r = r, so an element with this remainder must be paired with another element that also has the same remainder. Consequently, the count of elements with remainder k/2 must be even.

If all these conditions hold, we can form the pairs, so we return true. Otherwise, it's impossible, and we return false.

1class Solution {2    public boolean canArrange(int[] arr, int k) {3        int[] remainderCounts = new int[k];4        for (int num : arr) {5            int rem = ((num % k) + k) % k;6            remainderCounts[rem]++;7        }8 9        // Condition 1: Count of numbers with remainder 0 must be even.10        if (remainderCounts[0] % 2 != 0) {11            return false;12        }13 14        // Condition 2: For r from 1 to k/2, check complementary pairs.15        for (int r = 1; r <= k / 2; r++) {16            // If r is its own complement (only when k is even and r = k/2)17            if (r * 2 == k) {18                if (remainderCounts[r] % 2 != 0) {19                    return false;20                }21            } else {22                // For all other r, count(r) must equal count(k-r).23                if (remainderCounts[r] != remainderCounts[k - r]) {24                    return false;25                }26            }27        }28 29        return true;30    }31}

Complexity

Time

O(n + k). We iterate through the input array of size `n` once to build the frequency map, and then we iterate through the frequency array of size `k` (or `k/2`) once to check the conditions.

Space

O(k), as we need an auxiliary array of size `k` to store the frequencies of the remainders.

Trade-offs

Pros

Highly efficient with linear time complexity.
Optimal solution for the given constraints.
Handles all edge cases, including negative numbers, correctly and elegantly.

Cons

Requires extra space proportional to k, which could be large if k is very large (though it's fine for the given constraints).

This approach attempts to solve the problem by exploring every possible way to form pairs from the array elements. It uses a classic backtracking algorithm to try all combinations. If it finds any single valid partition of the array into n/2 pairs where each pair's sum is divisible by k, it concludes that it's possible and returns true.

Algorithm

Initialize a boolean array used of size n to false to track which elements have been paired.
Define a recursive helper function, for example, findPairs(arr, k, used, pairsFormed).
Base Case: If pairsFormed equals n / 2, it means all elements have been successfully paired. Return true.
Recursive Step:
- Find the first element arr[i] that has not been used yet (used[i] is false).
- Mark arr[i] as used (used[i] = true).
- Iterate through the subsequent elements arr[j] (where j > i).
- If arr[j] is not used and (arr[i] + arr[j]) % k == 0, we have found a potential pair.
- Mark arr[j] as used and make a recursive call findPairs(arr, k, used, pairsFormed + 1).
- If the recursive call returns true, it means a full valid partition was found, so we return true up the call stack.
- If the call returns false, we must backtrack. Unmark arr[j] as used (used[j] = false) and continue searching for another partner for arr[i].
If the loop finishes without finding a suitable partner for arr[i], it's impossible to form a valid partition from this state. We backtrack by unmarking arr[i] and return false.

Walkthrough

The core idea is to build the pairs one by one. We use a boolean array used to keep track of elements that have already been included in a pair.

A recursive function, say findPairs, attempts to form the remaining pairs. The function finds the first available element arr[i] and tries to pair it with every other available element arr[j]. If (arr[i] + arr[j]) % k == 0, we tentatively form this pair, mark both elements as used, and then recursively call the function to form the next pair from the remaining elements.

If a recursive call eventually leads to a state where all n/2 pairs are formed, we have found a solution. If a path leads to a dead end (e.g., an element cannot be paired with any remaining element), we "backtrack" by undoing the last pair formation and trying a different option.

1class Solution {2    public boolean canArrange(int[] arr, int k) {3        boolean[] used = new boolean[arr.length];4        return findPairs(arr, k, used, 0);5    }6 7    private boolean findPairs(int[] arr, int k, boolean[] used, int pairsFormed) {8        if (pairsFormed == arr.length / 2) {9            return true;10        }11 12        // Find the first unused element's index13        int i = -1;14        for (int idx = 0; idx < arr.length; idx++) {15            if (!used[idx]) {16                i = idx;17                break;18            }19        }20 21        if (i == -1) {22            // Should not be reached if pairsFormed < arr.length / 223            return true; 24        }25 26        used[i] = true;27 28        // Try to find a pair for arr[i]29        for (int j = i + 1; j < arr.length; j++) {30            if (!used[j]) {31                // Note: The problem statement guarantees arr[i] can be negative.32                // A simple (a + b) % k == 0 works for both positive and negative numbers in Java33                // as long as we are just checking for a zero result.34                if ((arr[i] + arr[j]) % k == 0) {35                    used[j] = true;36                    if (findPairs(arr, k, used, pairsFormed + 1)) {37                        return true;38                    }39                    used[j] = false; // Backtrack40                }41            }42        }43 44        used[i] = false; // Backtrack45        return false;46    }47}

Complexity

Time

O((n-1)!!) which is approximately O((n/2)!). This is factorial-level complexity, arising from the number of ways to partition `n` items into `n/2` pairs. It is computationally infeasible for the given constraints.

Space

O(n) for the recursion stack depth and the `used` boolean array.

Trade-offs

Pros

Conceptually straightforward as it directly models the problem of trying all pairings.

Cons

Extremely inefficient and slow.
Guaranteed to cause a 'Time Limit Exceeded' (TLE) error for the constraints specified in the problem (n up to 10^5).
Not a practical solution for anything beyond very small input sizes.

Solutions

Solution

1class Solution {2public3  boolean canArrange(int[] arr, int k) {4    int[] cnt = new int[k];5    for (int x : arr) {6      ++cnt[(x % k + k) % k];7    }8    for (int i = 1; i < k; ++i) {9      if (cnt[i] != cnt[k - i]) {10        return false;11      }12    }13    return cnt[0] % 2 == 0;14  }15}

1function canArrange ( 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 ; }

1class Solution {2public:3  bool canArrange(vector<int> &arr, int k) {4    vector<int> cnt(k);5    for (int &x : arr) {6      ++cnt[((x % k) + k) % k];7    }8    for (int i = 1; i < k; ++i) {9      if (cnt[i] != cnt[k - i]) {10        return false;11      }12    }13    return cnt[0] % 2 == 0;14  }15};

1class Solution:2    def canArrange(self, arr: List[int], k: int) -> bool: cnt = Counter(x % k for x in arr) return cnt[0] % 2 == 0 and all(cnt[i] == cnt[k - i] for i in range(1, k))

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem