Given an array arr[] of size N and an integer K, the task is to find the minimum count of pairs required to be removed such that no pair exists in the array whose sum of elements is equal to K.
Examples:
Input: arr[] = { 3, 1, 3, 4, 3 }, K = 6
Output: 1
Explanation:
Removing the pair (arr[0], arr[2]) modifies arr[] to arr[] = { 1, 4, 3 }
Since no pair exists in arr[] whose sum of elements is equal to K(=6), the required output is 1.Input: arr = { 1, 2, 3, 4 }, K = 5
Output: 2
Explanation:
Removing the pair (arr[0], arr[3]) modifies arr[] to arr[] = { 2, 3 }
Removing the pair (arr[0], arr[1]) modifies arr[] to arr[] = { }
Since no pair exists in arr[] whose sum of elements is equal to K(=5), the required output is 2.
Approach: The problem can be solved using the two-pointer technique. Follow the steps below to solve this problem:
- Sort the array in ascending order.
- Initialize two variables, say left = 0 and right = N – 1 to store the index of left and right pointers respectively.
- Initialize a variable, say cntPairs, to store the minimum count of pairs required to be removed such that no pair exists in the array whose sum is equal to K.
- Traverse the array and check the following conditions.
- If arr[left] + arr[right] == K, then increment the value of cntPairs by 1 and update left += 1 and right -= 1.
- If arr[left] + arr[right] < K, then update left += 1.
- If arr[left] + arr[right] < K, then update right -= 1.
- Finally, print the value of cntPairs.
Below is the implementation of the above approach:
C++14
// C++14 program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum count of pairs// required to be removed such that no pairs// exist whose sum equal to Kint maxcntPairsSumKRemoved(vector<int> arr, int k){ // Stores maximum count of pairs required // to be removed such that no pairs // exist whose sum equal to K int cntPairs = 0; // Base Case if (arr.size() <= 1) return cntPairs; // Sort the array sort(arr.begin(), arr.end()); // Stores index of // left pointer int left = 0; // Stores index of // right pointer int right = arr.size() - 1; while (left < right) { // Stores sum of left // and right pointer int s = arr[left] + arr[right]; // If s equal to k if (s == k) { // Update cntPairs cntPairs += 1; // Update left left += 1; // Update right right -= 1; } // If s > k else if (s > k) // Update right right -= 1; else // Update left left += 1; } // Return the cntPairs return cntPairs;}// Driver Codeint main(){ vector<int> arr = { 1, 2, 3, 4 }; int K = 5; // Function call cout << (maxcntPairsSumKRemoved(arr, K)); return 0;}// This code is contributed by mohit kumar 29 |
Java
// Java program for the above approach import java.util.*;class GFG{ // Function to find the maximum count of pairs// required to be removed such that no pairs// exist whose sum equal to Kstatic int maxcntPairsSumKRemoved(int[] arr, int k){ // Stores maximum count of pairs required // to be removed such that no pairs // exist whose sum equal to K int cntPairs = 0; // Base Case if (arr.length <= 1) return cntPairs; // Sort the array Arrays.sort(arr); // Stores index of // left pointer int left = 0; // Stores index of // right pointer int right = arr.length - 1; while (left < right) { // Stores sum of left // and right pointer int s = arr[left] + arr[right]; // If s equal to k if (s == k) { // Update cntPairs cntPairs += 1; // Update left left += 1; // Update right right -= 1; } // If s > k else if (s > k) // Update right right -= 1; else // Update left left += 1; } // Return the cntPairs return cntPairs;} // Driver Code public static void main (String[] args) { int[] arr = { 1, 2, 3, 4 }; int K = 5; // Function call System.out.println (maxcntPairsSumKRemoved(arr, K)); }} |
Python3
# Python3 program to implement# the above approach# Function to find the maximum count of pairs# required to be removed such that no pairs # exist whose sum equal to Kdef maxcntPairsSumKRemoved(arr, k): # Stores maximum count of pairs required # to be removed such that no pairs # exist whose sum equal to K cntPairs = 0 # Base Case if not arr or len(arr) == 1: return cntPairs # Sort the array arr.sort() # Stores index of # left pointer left = 0 # Stores index of # right pointer right = len(arr) - 1 while left < right: # Stores sum of left # and right pointer s = arr[left] + arr[right] # If s equal to k if s == k: # Update cntPairs cntPairs += 1 # Update left left += 1 # Update right right-= 1 # If s > k elif s > k: # Update right right-= 1 else: # Update left left+= 1 # Return the cntPairs return cntPairs # Driver Code if __name__ == "__main__": arr =[1, 2, 3, 4] K = 5 # Function call print(maxcntPairsSumKRemoved(arr, K)) |
C#
// C# program for the above approach using System;class GFG{ // Function to find the maximum count of pairs// required to be removed such that no pairs// exist whose sum equal to Kstatic int maxcntPairsSumKRemoved(int[] arr, int k){ // Stores maximum count of pairs required // to be removed such that no pairs // exist whose sum equal to K int cntPairs = 0; // Base Case if (arr.Length <= 1) return cntPairs; // Sort the array Array.Sort(arr); // Stores index of // left pointer int left = 0; // Stores index of // right pointer int right = arr.Length - 1; while (left < right) { // Stores sum of left // and right pointer int s = arr[left] + arr[right]; // If s equal to k if (s == k) { // Update cntPairs cntPairs += 1; // Update left left += 1; // Update right right -= 1; } // If s > k else if (s > k) // Update right right -= 1; else // Update left left += 1; } // Return the cntPairs return cntPairs;} // Driver Code public static void Main(String[] args) { int[] arr = { 1, 2, 3, 4 }; int K = 5; // Function call Console.WriteLine (maxcntPairsSumKRemoved(arr, K)); }}// This code is contributed by 29AjayKumar |
Javascript
<script>//Javascript program to implement// the above approach// Function to find the maximum count of pairs// required to be removed such that no pairs// exist whose sum equal to Kfunction maxcntPairsSumKRemoved( arr, k){ // Stores maximum count of pairs required // to be removed such that no pairs // exist whose sum equal to K var cntPairs = 0; // Base Case if (arr.length <= 1) return cntPairs; // Sort the array arr.sort(); // Stores index of // left pointer var left = 0; // Stores index of // right pointer var right = arr.length - 1; while (left < right) { // Stores sum of left // and right pointer var s = arr[left] + arr[right]; // If s equal to k if (s == k) { // Update cntPairs cntPairs += 1; // Update left left += 1; // Update right right -= 1; } // If s > k else if (s > k) // Update right right -= 1; else // Update left left += 1; } // Return the cntPairs return cntPairs;}var arr = [ 1,2,3,4];var K = 5; // Function calldocument.write(maxcntPairsSumKRemoved(arr, K));//This code is contributed by SoumikMondal</script> |
Output:
2
Time Complexity: O(N*logN) as it sorts the given array
Auxiliary Space: O(1)
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!
