Determine whether an array can be divided into pairs with a sum divisible by `k`
Given an integer array, determine whether it can be divided into pairs such that the sum of elements in each pair is divisible by a given positive integer k.
For example,
Input:
arr[] = { 3, 1, 2, 6, 9, 4 }
k = 5
Output: Pairs can be formed
Explanation: Array can be divided into pairs {(3, 2), (1, 9), (4, 6)} where the sum of elements in each pair is divisible by 5.
Input:
arr[] = { 2, 9, 4, 1, 3, 5 }
k = 6
Output: Pairs can be formed
Explanation: Array can be divided into pairs {(2, 4), (9, 3), (1, 5)} where the sum of elements in each pair is divisible by 6.
Input:
arr[] = { 3, 1, 2, 6, 9, 4 }
k = 6
Output: Pairs cannot be formed
Explanation: Array cannot be divided into pairs where the sum of elements in each pair is divisible by 6.
arr[] = { 3, 1, 2, 6, 9, 4 }
k = 5
Output: Pairs can be formed
Explanation: Array can be divided into pairs {(3, 2), (1, 9), (4, 6)} where the sum of elements in each pair is divisible by 5.
Input:
arr[] = { 2, 9, 4, 1, 3, 5 }
k = 6
Output: Pairs can be formed
Explanation: Array can be divided into pairs {(2, 4), (9, 3), (1, 5)} where the sum of elements in each pair is divisible by 6.
Input:
arr[] = { 3, 1, 2, 6, 9, 4 }
k = 6
Output: Pairs cannot be formed
Explanation: Array cannot be divided into pairs where the sum of elements in each pair is divisible by 6.
1. Brute-Force Solution
A naive solution is to iterate over array arr and consider each element arr[i] as the first element of a pair. Then process the remaining elements to find the first non-visited element arr[j] which satisfies the relation (arr[j] + arr[i]) % k == 0. If a pair is found for all elements, return true; otherwise, return false.
The time complexity of this approach is O(n2), where n is the input size and requires O(n) extra space. Following is the C, Java, and Python program that demonstrates it:
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
#include <stdio.h> // Determine if an array can be divided into pairs such that the sum of elements // in each pair is divisible by the given integer `k` int findPairs(int arr[], int n, int k) { // base case: input contains an odd number of elements // (an odd number of elements cannot be paired) if (n & 1) { return 0; } // create a boolean array to mark elements that formed a pair int visited[n]; // initialize visited array by value 0 for (int i = 0; i < n; i++) { visited[i] = 0; } // consider each element as the first element of a pair for (int i = 0; i < n - 1; i++) { // ignore the current element if it is already part of another pair if (visited[i]) { continue; } // find the first non-visited element `arr[j]` that forms a pair with `arr[i]` int j = i + 1; while (j < n) { if (!visited[j] && (arr[j] + arr[i]) % k == 0) { // pair found `(arr[i], arr[j])` visited[j] = 1; break; } j++; } // return 0 if pair not found for the current element if (j == n) { return 0; } } // we reach here only when each element forms a pair return 1; } int main(void) { int arr[] = { 2, 9, 4, 1, 3, 5 }; int n = sizeof(arr) / sizeof(arr[0]); int k = 6; if (findPairs(arr, n, k)) { printf("Pairs can be formed"); } else { printf("Pairs cannot be formed"); } return 0; } |
Output:
Pairs can be formed
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
class Main { // Determine if an array can be divided into pairs such that the sum of elements // in each pair is divisible by the given integer `k` public static int findPairs(int[] arr, int k) { // base case: input contains an odd number of elements // (an odd number of elements cannot be paired) if (arr.length % 2 == 1) { return 0; } // create a boolean array to mark elements that formed a pair int[] visited = new int[arr.length]; // initialize visited array by value 0 for (int i = 0; i < arr.length; i++) { visited[i] = 0; } // consider each element as the first element of a pair for (int i = 0; i < arr.length - 1; i++) { // ignore the current element if it is already part of another pair if (visited[i] != 0) { continue; } // find the first non-visited element `arr[j]` that forms a pair with // `arr[i]` int j = i + 1; while (j < arr.length) { if (visited[j] == 0 && (arr[j] + arr[i]) % k == 0) { // pair found `(arr[i], arr[j])` visited[j] = 1; break; } j++; } // return 0 if pair not found for the current element if (j == arr.length) { return 0; } } // we reach here only when each element forms a pair return 1; } public static void main(String[] args) { int[] arr = { 2, 9, 4, 1, 3, 5 }; int k = 6; if (findPairs(arr, k) != 0) { System.out.println("Pairs can be formed"); } else { System.out.println("Pairs cannot be formed"); } } } |
Output:
Pairs can be formed
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
# Determine if an array can be divided into pairs such that the sum of elements # in each pair is divisible by the given integer `k` def findPairs(arr, k): # base case: input contains an odd number of elements # (an odd number of elements cannot be paired) if len(arr) & 1: return 0 # create a boolean array to mark elements that formed a pair visited = [0] * len(arr) # consider each element as the first element of a pair for i in range(len(arr) - 1): # ignore the current element if it is already part of another pair if visited[i]: continue # find the first non-visited element `arr[j]` that forms a pair with `arr[i]` j = i + 1 while j < len(arr): if not visited[j] and (arr[j] + arr[i]) % k == 0: # pair found `(arr[i], arr[j])` visited[j] = 1 break j += 1 # return 0 if pair not found for the current element if j == len(arr): return 0 # we reach here only when each element forms a pair return 1 if __name__ == '__main__': arr = [2, 9, 4, 1, 3, 5] k = 6 if findPairs(arr, k): print("Pairs can be formed") else: print("Pairs cannot be formed") |
Output:
Pairs can be formed
2. Hashing Solution
We can improve the time complexity to O(n) using hashing. The idea is to traverse the input array and create a map to keep track of remainders of all input elements with k, i.e., create a map whose keys store the remainder and value stores the frequency of the remainder. Then traverse all (remainder, frequency) pairs present on the map.
- For elements directly divisible by
k, the remainderrwould be 0, and the frequency should be even. - For elements not directly divisible by
kand having remainderr, a pair only exists when there is another array element with remainderk-r. Therefore, the frequency of the remainderrmust be equal to the frequency ofk-r.
If this is not the case for any remainder r in the map, return false; otherwise, return true. Following is the C, C++, Java, and Python program that demonstrates it:
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
#include <stdio.h> // Determine if an array can be divided into pairs such that the sum of elements // in each pair is divisible by the given integer `k` int findPairs(int arr[], int n, int k) { // base case: input contains an odd number of elements // (an odd number of elements cannot be paired) if (n & 1) { return 0; } // create a count array to keep track of all input elements with `k` int freq[k]; // initialize the count array by value 0 for (int i = 0; i < n; i++) { freq[i] = 0; } // consider each element for (int i = 0; i < n; i++) { // calculate the remainder of the current element with `k` int r = arr[i] % k; // increment the count array freq[r]++; } // the frequency of elements directly divisible by `k` must be even if (freq[0] % 2 != 0) { return 0; } // for each element with remainder `r`, there should be an element with // remainder `k-r` for (int r = 1; r <= k / 2; r++) { if (freq[r] != freq[k - r]) { return 0; } } // we reach here only when each element forms a pair return 1; } int main(void) { int arr[] = { 2, 9, 4, 1, 3, 5 }; int n = sizeof(arr) / sizeof(arr[0]); int k = 6; if (findPairs(arr, n, k)) { printf("Pairs can be formed"); } else { printf("Pairs cannot be formed"); } return 0; } |
Output:
Pairs can be formed
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
#include <iostream> #include <vector> #include <unordered_map> using namespace std; // Determine if an array can be divided into pairs such that the sum of elements // in each pair is divisible by the given integer `k` bool findPairs(vector<int> const &input, int k) { // base case: input contains an odd number of elements // (an odd number of elements cannot be paired) if (input.size() & 1) { return false; } // create a frequency map unordered_map<int, int> map; // add the remainder of each input element `i` with `k` to the frequency map for (int i: input) { map[i % k] += 1; } // traverse (remainder, frequency) pairs present on the map for (auto const &pair: map) { int r = pair.first; int f = pair.second; // if the remainder is 0 if (r == 0) { // return false if the frequency of the remainder is odd if (f % 2 != 0) { return false; } } // otherwise, the frequency of the remainder `r` must be equal to // the frequency of `k-r` else if (f != map[k - r]) { return false; } } return true; } int main() { vector<int> input = { 2, 9, 4, 1, 3, 5 }; int k = 6; if (findPairs(input, k)) { printf("Pairs can be formed"); } else { printf("Pairs cannot be formed"); } return 0; } |
Output:
Pairs can be formed
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
class Main { // Determine if an array can be divided into pairs such that the sum of elements // in each pair is divisible by the given integer `k` public static boolean findPairs(int[] arr, int k) { // base case: input contains an odd number of elements // (an odd number of elements cannot be paired) if ((arr.length & 1) == 1) { return false; } // create a count array to keep track of the remainder of // input elements with `k` int[] freq = new int[k]; // consider each element for (int i = 0; i < arr.length; i++) { // calculate the remainder of the current element with `k` int r = arr[i] % k; // increment the count array freq[r]++; } // the frequency of elements directly divisible by `k` must be even if (freq[0] % 2 != 0) { return false; } // for each element with remainder `r`, there should be an element with // remainder `k-r` for (int r = 1; r <= k / 2; r++) { if (freq[r] != freq[k - r]) { return false; } } // we reach here only when each element forms a pair return true; } public static void main(String[] args) { int[] arr = { 2, 9, 4, 1, 3, 5 }; int k = 6; if (findPairs(arr, k)) { System.out.println("Pairs can be formed"); } else { System.out.println("Pairs cannot be formed"); } } } |
Output:
Pairs can be formed
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
# Determine if an array can be divided into pairs such that the sum of elements # in each pair is divisible by the given integer `k` def findPairs(arr, k): # base case: input contains an odd number of elements # (an odd number of elements cannot be paired) if len(arr) & 1: return False # create a count array to keep track of the remainder of input elements with `k` freq = [0] * k # consider each element for i in range(len(arr)): # calculate the remainder of the current element with `k` r = arr[i] % k # increment the count array freq[r] += 1 # the frequency of elements directly divisible by `k` must be even if freq[0] % 2 != 0: return False # for each element with remainder `r`, there should be an element with # remainder `k-r` for r in range(1, k // 2 + 1): if freq[r] != freq[k - r]: return False # we reach here only when each element forms a pair return True if __name__ == '__main__': arr = [2, 9, 4, 1, 3, 5] k = 6 if findPairs(arr, k): print("Pairs can be formed") else: print("Pairs cannot be formed") |
Output:
Pairs can be formed
The time complexity of the above solution is O(n) and requires O(k) extra space.
Note that the above solution won’t work for negative numbers. To handle the negative numbers, increment the negative remainder r by k before updating the count array/map, as shown below:
|
1 2 3 |
if (r < 0) { r += k; } |
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)