Given an array of N integers and an integer K. The task is to print the maximum number of pairs(a[i]+a[j]) possible which are divisible by K.
Note: A particular index number cannot be considered in more than one pair.
Examples:
Input: a[] = {1, 2, 2, 3, 2, 4, 10}, k =2
Output: 3
The pairs are: (1, 2), (4, 5), (0, 3)
Input: a[] = {1, 2, 2, 3, 2, 4, 5}, k = 3
Output: 2
Naive Approach: A naive approach is to iterate using two loops and calculate the total number of pairs whose sum is divisible by K.
Time Complexity: O(N^2), as we will be using nested loops for traversing N*N times. Where N is the number of elements in the array.
Auxiliary Space: O(1), as we will be not using any extra space.
Efficient Approach: An efficient approach will be to use a hashing technique to solve the problem. The following steps can be followed to solve the above problem.
- Initially increase the hash[a[i]%k] by one for every array element.
- Iterate in the map and get every possible hash values.
- If the hash value is 0, then the number of pairs will be hash[0]/2.
- After that for every hash value x, we can use the minimum of (hash[x], hash[k-x]) and use them to create pairs.
- Subtract the number of pairs used from the hash value accordingly.
Below is the implementation of the above approach.
C++
// C++ program to implement the above// approach#include <bits/stdc++.h>using namespace std;// Function to maximize the number of pairsint findMaximumPairs(int a[], int n, int k){ // Hash-table unordered_map<int, int> hash; for (int i = 0; i < n; i++) hash[a[i] % k]++; int count = 0; // Iterate for all numbers less than hash values for (auto it : hash) { // If the number is 0 if (it.first == 0) { // We take half since same number count += it.second / 2; if (it.first % 2 == 0) hash[it.first] = 0; else hash[it.first] = 1; } else { int first = it.first; int second = k - it.first; // Check for minimal occurrence if (hash[first] < hash[second]) { // Take the minimal count += hash[first]; // Subtract the pairs used hash[second] -= hash[first]; hash[first] = 0; } else if (hash[first] > hash[second]) { // Take the minimal count += hash[second]; // Subtract the pairs used hash[first] -= hash[second]; hash[second] = 0; } else { // Check if numbers are same if (first == second) { // If same then number of pairs will be half count += it.second / 2; // Check for remaining if (it.first % 2 == 0) hash[it.first] = 0; else hash[it.first] = 1; } else { // Store the number of pairs count += hash[first]; hash[first] = 0; hash[second] = 0; } } } } return count;}// Driver codeint main(){ int a[] = { 1, 2, 2, 3, 2, 4, 10 }; int n = sizeof(a) / sizeof(a[0]); int k = 2; cout << findMaximumPairs(a, n, k); return 0;} |
Java
// Java program to implement the above// approachimport java.util.*;class GFG{// Function to maximize the number of pairsstatic int findMaximumPairs(int a[], int n, int k){ // Hash-table HashMap<Integer,Integer> hash = new HashMap<Integer,Integer>(); for (int i = 0; i < n; i++) if(hash.containsKey(a[i] % k)){ hash.put(a[i] % k, hash.get(a[i] % k)+1); } else{ hash.put(a[i] % k, 1); } int count = 0; // Iterate for all numbers less than hash values for (Map.Entry<Integer,Integer> it : hash.entrySet()){ // If the number is 0 if (it.getKey() == 0) { // We take half since same number count += it.getValue() / 2; if (it.getKey() % 2 == 0) hash.put(it.getKey(), 0); else hash.put(it.getKey(), 1); } else { int first = it.getKey(); int second = k - it.getKey(); // Check for minimal occurrence if (hash.get(first) < hash.get(second)) { // Take the minimal count += hash.get(first); // Subtract the pairs used hash.put(second, hash.get(second)-hash.get(first)); hash.put(first, 0); } else if (hash.get(first) > hash.get(second)) { // Take the minimal count += hash.get(second); // Subtract the pairs used hash.put(first, hash.get(first)-hash.get(second)); hash.put(second, 0); } else { // Check if numbers are same if (first == second) { // If same then number of pairs will be half count += it.getValue() / 2; // Check for remaining if (it.getKey() % 2 == 0) hash.put(it.getKey(), 0); else hash.put(it.getKey(), 1); } else { // Store the number of pairs count += hash.get(first); hash.put(first, 0); hash.put(second, 0); } } } } return count;}// Driver codepublic static void main(String[] args){ int a[] = { 1, 2, 2, 3, 2, 4, 10 }; int n = a.length; int k = 2; System.out.print(findMaximumPairs(a, n, k));}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program to implement # the above approach # Function to maximize the# number of pairs def findMaximumPairs(a, n, k) : # Hash-table hash = {}; for i in range(n) : if a[i] % k not in hash : hash[a[i] % k] = 0 hash[a[i] % k] += 1 count = 0; # Iterate for all numbers less # than hash values for keys,values in hash.items() : # If the number is 0 if (keys == 0) : # We take half since same number count += values // 2; if (keys % 2 == 0) : hash[keys] = 0; else : hash[keys] = 1; else : first = keys; second = k -keys; # Check for minimal occurrence if (hash[first] < hash[second]) : # Take the minimal count += hash[first]; # Subtract the pairs used hash[second] -= hash[first]; hash[first] = 0; elif (hash[first] > hash[second]) : # Take the minimal count += hash[second]; # Subtract the pairs used hash[first] -= hash[second]; hash[second] = 0; else : # Check if numbers are same if (first == second) : # If same then number of pairs # will be half count += values // 2; # Check for remaining if (keys % 2 == 0) : hash[keys] = 0; else : hash[keys] = 1; else : # Store the number of pairs count += hash[first]; hash[first] = 0; hash[second] = 0; return count; # Driver code if __name__ == "__main__" : a = [ 1, 2, 2, 3, 2, 4, 10 ]; n = len(a) k = 2; print(findMaximumPairs(a, n, k)); # This code is contributed by Ryuga |
C#
using System;using System.Collections.Generic;public class MainClass { public static int FindMaximumPairs(int[] a, int n, int k) { // Hash-table Dictionary<int, int> hash = new Dictionary<int, int>(); for (int i = 0; i < n; i++) { if (!hash.ContainsKey(a[i] % k)) { hash[a[i] % k] = 0; } hash[a[i] % k]++; } int count = 0; // Iterate for all numbers less than hash values foreach (KeyValuePair<int, int> kvp in new Dictionary<int, int>(hash)) { int keys = kvp.Key; int values = kvp.Value; // If the number is 0 if (keys == 0) { // We take half since same number count += values / 2; if (keys % 2 == 0) { hash[keys] = 0; } else { hash[keys] = 1; } } else { int first = keys; int second = k - keys; // Check for minimal occurrence if (hash[first] < hash[second]) { // Take the minimal count += hash[first]; // Subtract the pairs used hash[second] -= hash[first]; hash[first] = 0; } else if (hash[first] > hash[second]) { // Take the minimal count += hash[second]; // Subtract the pairs used hash[first] -= hash[second]; hash[second] = 0; } else { // Check if numbers are same if (first == second) { // If same then number of pairs will be half count += values / 2; // Check for remaining if (keys % 2 == 0) { hash[keys] = 0; } else { hash[keys] = 1; } } else { // Store the number of pairs count += hash[first]; hash[first] = 0; hash[second] = 0; } } } } return count; } public static void Main() { int[] a = { 1, 2, 2, 3, 2, 4, 10 }; int n = a.Length; int k = 2; Console.WriteLine(FindMaximumPairs(a, n, k)); }} |
Javascript
<script>// Javascript program to implement the above// approach// Function to maximize the number of pairsfunction findMaximumPairs(a, n, k) { // Hash-table let hash = new Map(); for (let i = 0; i < n; i++) { if (hash.has(a[i] % k)) { hash.set(a[i] % k, hash.get(a[i] % k) + 1) } else { hash.set(a[i] % k, 1) } } let count = 0; // Iterate for all numbers less than hash values for (let it of hash) { // If the number is 0 if (it[0] == 0) { // We take half since same number count += Math.floor(it[1] / 2); if (it[0] % 2 == 0) hash.set(it[0], 0); else hash.set(it[0], 1); } else { let first = it[0]; let second = k - it[0]; // Check for minimal occurrence if (hash.get(first) < hash.get(second)) { // Take the minimal count += hash.get(first); // Subtract the pairs used hash.set(second, hash.get(second) - hash.get(first)); hash.set(first, 0); } else if (hash.get(first) > hash.get(second)) { // Take the minimal count += hash.get(second); // Subtract the pairs used hash.set(first, hash.get(first) - hash.get(second)); hash.set(second, 0); } else { // Check if numbers are same if (first == second) { // If same then number of pairs will be half count += Math.floor(it[1] / 2); // Check for remaining if (it[0] % 2 == 0) hash.set(it[0], 0); else hash.set(it[0], 1); } else { // Store the number of pairs count += hash.get(first); hash.set(first, 0); hash.set(second, 0); } } } } return count;}// Driver codelet a = [1, 2, 2, 3, 2, 4, 10];let n = a.length;let k = 2;document.write(findMaximumPairs(a, n, k));// This code is contributed by _saurabh_jaiswal</script> |
Output:
3
Time Complexity: O(N), as we are using a loop to traverse N times. Where N is the number of elements in the array.
Auxiliary Space: O(N), as we are using extra space for the map. Where N is the number of elements in the array.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
