Given a sorted array of integers and a number k, write a function that returns true if given array can be divided into pairs such that sum of every pair k.
Expected time complexity O(n) and extra space O(1). This problem is a variation of below problem, but has a different interesting solution that requires only O(1) space.
Check if an array can be divided into pairs whose sum is divisible by k
Examples:
Input: arr[] = {1, 3, 3, 5}, k = 6
Output: True
We can divide array into (1, 5) and (3, 3).
Sum of both of these pairs is 6.
Input: arr[] = {2, 5, 5, 5, 5, 8}, k = 10
Output: True
We can divide array into (2, 8), (5, 5) and
(5, 5). Sum of all these pairs is 10.
We strongly recommend you to minimize your browser and try this yourself first.
A Simple Solution is to iterate through every element arr[i]. Find if there is another not yet visited element with value (k – arr[i]). If there is no such element, return false. If a pair is found, then mark both elements as visited. Time complexity of this solution is O(n2 and it requires O(n) extra space.
A Better Solution is to use Hashing. Solution given on this post can be easily modified to work. Time complexity of this solution is O9n) but it requires extra space for hash table.
An Efficient Solution is to use Meet in the Middle algorithm discussed in method 1 here.
1) Initialize two index variables
(a) Initialize first to the leftmost index: l = 0
(b) Initialize second the rightmost index: r = n-1
2) Loop while l < r.
(a) If (A[l] + A[r] != k) then return false
(b) Else r--, l++
Below is the implementation of above algorithm.
C++
// A C++ program to check if arr[0..n-1] can be divided// in pairs such that every pair has sum k.#include <bits/stdc++.h>using namespace std; // Returns true if arr[0..n-1] can be divided into pairs// with sum equal to k.bool canPairsSorted(int arr[], int n, int k){ // An odd length array cannot be divided into pairs if (n & 1) return false; // Traverse from both sides of array int l = 0, r = n-1; while (l < r) { // If array can be divided, then sum of current // elements must be sum if (arr[l] + arr[r] != k) return false; // Move index variables l++; r--; } return true;}/* Driver program to test above function */int main(){ int arr[] = {1, 2, 3, 3, 3, 3, 4, 5}; int k = 6; int n = sizeof(arr)/sizeof(arr[0]); canPairsSorted(arr, n, k)? cout << "True": cout << "False"; return 0;} |
Java
// Java program to check if arr[0..n-1] can be divided // in pairs such that every pair has sum k. class GFG {// Returns true if arr[0..n-1] can be divided into pairs // with sum equal to k. static boolean canPairs(int arr[], int n, int k) {// An odd length array cannot be divided into pairs if (n == 1) { return false; }// Traverse from both sides of array int l = 0, r = n - 1; while (l < r) { // If array can be divided, then sum of current // elements must be sum if (arr[l] + arr[r] != k) { return false; } // Move index variables l++; r--; } return true; }// Drivers code public static void main(String[] args) { int arr[] = {1, 2, 3, 3, 3, 3, 4, 5}; int k = 6; int n = arr.length; if (canPairs(arr, n, k)) { System.out.println("True"); } else { System.out.println("False"); } }}//This code contributed by 29AjayKumar |
Python 3
# A Python3 program to check if arr[0..n-1] can be # divided in pairs such that every pair has sum k.# Returns true if arr[0..n-1] can be divided # into pairs with sum equal to k.def canPairsSorted(arr, n, k): # An odd length array cannot # be divided into pairs if (n & 1): return False; # Traverse from both sides of array l = 0; r = n - 1; while (l < r): # If array can be divided, then # sum of current elements must be sum if (arr[l] + arr[r] != k): return False; # Move index variables l = l + 1; r = r - 1; return True# Driver Codearr = [1, 2, 3, 3, 3, 3, 4, 5]k = 6n = len(arr)if(canPairsSorted(arr, n, k)): print("True") else: print("False");# This code is contributed # by Akanksha Rai |
C#
// C# program to check if arr[0..n-1] // can be divided in pairs such that // every pair has sum k. using System;class GFG{// Returns true if arr[0..n-1] // can be divided into pairs // with sum equal to k. static bool canPairs(int []arr, int n, int k) { // An odd length array cannot // be divided into pairs if (n == 1) { return false; } // Traverse from both sides of array int l = 0, r = n - 1; while (l < r) { // If array can be divided, // then sum of current // elements must be sum if (arr[l] + arr[r] != k) { return false; } // Move index variables l++; r--; } return true;}// Driver code public static void Main() { int []arr = {1, 2, 3, 3, 3, 3, 4, 5}; int k = 6; int n = arr.Length; if (canPairs(arr, n, k)) { Console.Write("True"); } else { Console.Write("False"); }}}// This code is contributed by PrinciRaj |
Javascript
<script>// Java Script program to check if arr[0..n-1] can be divided// in pairs such that every pair has sum k.// Returns true if arr[0..n-1] can be divided into pairs// with sum equal to k. function canPairs(arr,n,k) {// An odd length array cannot be divided into pairs if (n == 1) { return false; }// Traverse from both sides of array let l = 0, r = n - 1; while (l < r) { // If array can be divided, then sum of current // elements must be sum if (arr[l] + arr[r] != k) { return false; } // Move index variables l++; r--; } return true; }// Drivers code let arr = [1, 2, 3, 3, 3, 3, 4, 5]; let k = 6; let n = arr.length; if (canPairs(arr, n, k)) { document.write("True"); } else { document.write("False"); }// This code is contributed by Gottumukkala Sravan Kumar (171fa07058)</script> |
PHP
<?php// A PHP program to check if arr[0..n-1] // can be divided in pairs such that // every pair has sum k.// Returns true if arr[0..n-1] can be // divided into pairs with sum equal to k.function canPairs(&$arr, $n, $k){ // An odd length array cannot be // divided into pairs if ($n & 1) return false; // Traverse from both sides of array $l = 0; $r = $n - 1; while ($l < $r) { // If array can be divided, then sum // of current elements must be sum if ($arr[$l] + $arr[$r] != $k) return false; // Move index variables $l++; $r--; } return true;}// Driver Code$arr = array(1, 2, 3, 3, 3, 3, 4, 5);$n = 6;$k = 6;$n = sizeof($arr);if (canPairs($arr, $n, $k)) echo ("True");else echo ("False");// This code is contributed// by Shivi_Aggarwal ?> |
Output
True
Time Complexity: O(n)
Auxiliary Space: O(1)
Approach#2: Using HashMap
This approach uses a HashMap to count the frequency of each element in the array. It then traverses the array and checks if the difference between the current element and the target value k is present in the HashMap and has a frequency greater than 0. If yes, it decrements the frequency of the difference element and moves to the next element in the array. If no, it returns False. Finally, if all elements can be paired, it returns True.
Algorihtm
1. Create a HashMap to store the frequency of each element in the array.
2. Traverse the array and for each element, check if the difference between the element and the target value k is. present in the HashMap and has a frequency greater than 0.
3. If yes, decrement the frequency of the difference element and move to the next element in the array.
4. If no, return False.
5. If all elements can be paired, return True.
C++
#include <bits/stdc++.h>using namespace std;bool can_be_divided_into_pairs(vector<int> arr, int k){ unordered_map<int, int> frequency_map; // Count frequency of each element in the array for (int element : arr) { frequency_map[element]++; } // Traverse the array and check if the element can be // paired for (int element : arr) { if (frequency_map[element] > 0) { int difference = k - element; if (frequency_map[difference] > 0) { frequency_map[element]--; frequency_map[difference]--; } else { return false; } } } return true;}int main(){ vector<int> arr = { 1, 2, 3, 3, 3, 3, 4, 5 }; int k = 6; if (can_be_divided_into_pairs(arr, k) == 1) { cout << "True" << endl; } else { cout << "False" << endl; }} |
Java
import java.util.HashMap;import java.util.Map;public class Main { public static boolean canBeDividedIntoPairs(int[] arr, int k) { // Create a HashMap to store the frequency of each element in the array Map<Integer, Integer> frequencyMap = new HashMap<>(); // Count the frequency of each element in the array for (int element : arr) { frequencyMap.put(element, frequencyMap.getOrDefault(element, 0) + 1); } // Traverse the array and check if the elements can be paired for (int element : arr) { if (frequencyMap.get(element) > 0) { int difference = k - element; if (frequencyMap.getOrDefault(difference, 0) > 0) { // Decrement the frequencies of both elements to mark them as paired frequencyMap.put(element, frequencyMap.get(element) - 1); frequencyMap.put(difference, frequencyMap.get(difference) - 1); } else { return false; // If no valid pair is found, return false } } } return true; // If all elements can be paired, return true } public static void main(String[] args) { int[] arr = {1, 2, 3, 3, 3, 3, 4, 5}; int k = 6; if (canBeDividedIntoPairs(arr, k)) { System.out.println("True"); } else { System.out.println("False"); } }} |
Python3
def can_be_divided_into_pairs(arr, k): frequency_map = {} # Count frequency of each element in the array for element in arr: frequency_map[element] = frequency_map.get(element, 0) + 1 # Traverse the array and check if the element can be paired for element in arr: if frequency_map[element] > 0: difference = k - element if difference in frequency_map and frequency_map[difference] > 0: frequency_map[element] -= 1 frequency_map[difference] -= 1 else: return False return Truearr = [1, 2, 3, 3, 3, 3, 4, 5]k = 6print(can_be_divided_into_pairs(arr, k)) |
C#
using System;using System.Collections.Generic;class GFG{ public static bool CanBeDividedIntoPairs(int[] arr, int k) { // Create a Dictionary to store the frequency of each element in the array Dictionary<int, int> frequencyMap = new Dictionary<int, int>(); // Count the frequency of each element in the array foreach (int element in arr) { if (frequencyMap.ContainsKey(element)) { frequencyMap[element]++; } else { frequencyMap[element] = 1; } } // Traverse the array and check if the elements can be paired foreach (int element in arr) { if (frequencyMap[element] > 0) { int difference = k - element; if (frequencyMap.ContainsKey(difference) && frequencyMap[difference] > 0) { // Decrement the frequencies of both elements to mark them as paired frequencyMap[element]--; frequencyMap[difference]--; } else { return false; // If no valid pair is found, return false } } } return true; // If all elements can be paired, return true } public static void Main(string[] args) { int[] arr = { 1, 2, 3, 3, 3, 3, 4, 5 }; int k = 6; if (CanBeDividedIntoPairs(arr, k)) { Console.WriteLine("True"); } else { Console.WriteLine("False"); } }} |
Javascript
function can_be_divided_into_pairs(arr, k) { let frequency_map = {}; // Count frequency of each element in the array for (let element of arr) { frequency_map[element] = (frequency_map[element] || 0) + 1; } // Traverse the array and check if the element can be paired for (let element of arr) { if (frequency_map[element] > 0) { let difference = k - element; if (difference in frequency_map && frequency_map[difference] > 0) { frequency_map[element] -= 1; frequency_map[difference] -= 1; } else { return false; } } } return true;}let arr = [1, 2, 3, 3, 3, 3, 4, 5];let k = 6;console.log(can_be_divided_into_pairs(arr, k)); |
Output
True
Time Complexity: O(n), where n is the length of the array.
Auxiliary Space: O(n), for the HashMap.
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!
