Count maximum possible pairs from an array having sum K

0 0 8 minutes read

Given an array arr[] consisting of N integers and an integer K, the task is to find the maximum number of pairs having a sum K possible from the given array.

Note: Every array element can be part of a single pair.

Examples:

Input: arr[] = {1, 2, 3, 4}, K = 5
Output: 2
Explanation: Pairs with sum K from the array are (1, 4), and (2, 3).

Input: arr[] = {3, 1, 3, 4, 3}, K = 6
Output: 1
Explanation: Pair with sum K from the array is (3, 3).

Two-Pointer Approach: The idea is to use the Two Pointer Technique. Follow the steps below to solve the problem:

Initialize the variable ans as 0 to store the maximum number of pairs with the sum K.
Sort the array arr[] in increasing order.
Initialize two index variables L as 0 and R as (N – 1) to find the candidate elements in the sorted array.
Iterate until L is less than R and do the following:
- Check if the sum of arr[L] and arr[R] is K or not. If found to be true, then increment ans and L by 1 and decrement R by 1.
- If the sum of arr[L] and arr[R] is less than K, then increment L by 1.
- Otherwise, decrement R by 1.
After the above steps, print the value of ans as the result.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to count the maximum number
// of pairs from given array with sum K
void maxPairs(int nums[], int n, int k)
{
 
  // Sort array in increasing order
  sort(nums, nums + n);
 
  // Stores the final result
  int result = 0;
 
  // Initialize the left and right pointers
  int start = 0, end = n - 1;
 
  // Traverse array until start < end
  while (start < end) {
 
    if (nums[start] + nums[end] > k)
 
      // Decrement right by 1
      end--;
 
    else if (nums[start] + nums[end] < k)
 
      // Increment left by 1
      start++;
 
    // Increment result and left
    // pointer by 1 and decrement
    // right pointer by 1
    else
    {
      start++;
      end--;
      result++;
    }
  }
 
  // Print the result
  cout << result << endl;;
}
 
// Driver Code
int main()
{
  int arr[] = { 1, 2, 3, 4 };
  int n = sizeof(arr)/sizeof(arr[0]);
  int K = 5;
 
  // Function Call
  maxPairs(arr, n, K);
 
  return 0;
}
 
// This code is contributed by AnkThon

Java

// Java program for the above approach
import java.io.*;
import java.util.*;
 
class GFG {
 
    // Function to count the maximum number
    // of pairs from given array with sum K
    public static void maxPairs(int[] nums, int k)
    {
        // Sort array in increasing order
        Arrays.sort(nums);
 
        // Stores the final result
        int result = 0;
 
        // Initialize the left and right pointers
        int start = 0, end = nums.length - 1;
 
        // Traverse array until start < end
        while (start < end) {
 
            if (nums[start] + nums[end] > k)
 
                // Decrement right by 1
                end--;
 
            else if (nums[start] + nums[end] < k)
 
                // Increment left by 1
                start++;
 
            // Increment result and left
            // pointer by 1 and decrement
            // right pointer by 1
            else {
                start++;
                end--;
                result++;
            }
        }
 
        // Print the result
        System.out.println(result);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int[] arr = { 1, 2, 3, 4 };
        int K = 5;
 
        // Function Call
        maxPairs(arr, K);
    }
}

Python3

# Python3 program for the above approach
 
# Function to count the maximum number
# of pairs from given array with sum K
def maxPairs(nums, k):
     
    # Sort array in increasing order
    nums = sorted(nums)
 
    # Stores the final result
    result = 0
 
    # Initialize the left and right pointers
    start, end = 0, len(nums) - 1
     
    # Traverse array until start < end
    while (start < end):
        if (nums[start] + nums[end] > k):
 
            # Decrement right by 1
            end -= 1
 
        elif (nums[start] + nums[end] < k):
 
            # Increment left by 1
            start += 1
             
        # Increment result and left
        # pointer by 1 and decrement
        # right pointer by 1
        else:
            start += 1
            end -= 1
            result += 1
 
    # Print the result
    print(result)
 
# Driver Code
if __name__ == '__main__':
     
    arr = [ 1, 2, 3, 4 ]
    K = 5
 
    # Function Call
    maxPairs(arr, K)
     
# This code is contributed by mohit kumar 29

C#

// C# program for the above approach 
using System;
  
class GFG{
      
    // Function to count the maximum number
    // of pairs from given array with sum K
    public static void maxPairs(int[] nums, int k)
    {
       
        // Sort array in increasing order
        Array.Sort(nums);
  
        // Stores the final result
        int result = 0;
  
        // Initialize the left and right pointers
        int start = 0, end = nums.Length - 1;
  
        // Traverse array until start < end
        while (start < end) {
  
            if (nums[start] + nums[end] > k)
  
                // Decrement right by 1
                end--;
  
            else if (nums[start] + nums[end] < k)
  
                // Increment left by 1
                start++;
  
            // Increment result and left
            // pointer by 1 and decrement
            // right pointer by 1
            else
            {
                start++;
                end--;
                result++;
            }
        }
  
        // Print the result
        Console.Write(result);
    }
  
// Driver Code    
public static void Main()
{
  int[] arr = { 1, 2, 3, 4 };
  int K = 5;
   
  // Function Call
  maxPairs(arr, K);
}
}
 
// This code is contributed by susmitakundugoaldanga

Javascript

<script>
 
    // JavaScript program for above approach
 
    // Function to count the maximum number
    // of pairs from given array with sum K
    function maxPairs(nums, k)
    {
        // Sort array in increasing order
        nums.sort();
  
        // Stores the final result
        let result = 0;
  
        // Initialize the left and right pointers
        let start = 0, end = nums.length - 1;
  
        // Traverse array until start < end
        while (start < end) {
  
            if (nums[start] + nums[end] > k)
  
                // Decrement right by 1
                end--;
  
            else if (nums[start] + nums[end] < k)
  
                // Increment left by 1
                start++;
  
            // Increment result and left
            // pointer by 1 and decrement
            // right pointer by 1
            else {
                start++;
                end--;
                result++;
            }
        }
  
        // Print the result
        document.write(result);
    }
 
// Driver Code
 
           let arr = [ 1, 2, 3, 4 ];
        let K = 5;
  
        // Function Call
        maxPairs(arr, K);
 
</script>

Output:

Time Complexity: O(N*log N)
Auxiliary Space: O(1)

Efficient Approach: To optimize the above approach, the idea is to use hashing. Follow the steps below to solve the problem:

Initialize a variable, say ans, to store the maximum number of pairs with the sum K.
Initialize a hash table, say S, to store the frequency of elements in arr[].
Traverse the array arr[] using a variable, say i, and perform the following steps:
- If the frequency of (K – arr[i]) is positive, then increment ans by 1 and decrement the frequency of (K – arr[i]) by 1.
- Otherwise, insert arr[i] with frequency 1 in the Hash Table.
After completing the above steps, print the value of ans as the result.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
#include <string.h>
using namespace std;
 
// Function to find the maximum number
// of pairs with a sum K such that
// same element can't be used twice
void maxPairs(vector<int> nums, int k)
{
     
    // Initialize a hashm
    map<int, int> m;
     
    // Store the final result
    int result = 0;
 
    // Iterate over the array nums[]
    for(auto i : nums) 
    {
         
        // Decrement its frequency
        // in m and increment
        // the result by 1
        if (m.find(i) != m.end() && m[i] > 0)
        {
            m[i] = m[i] - 1;
            result++;
        }
 
        // Increment its frequency by 1
        // if it is already present in m.
        // Otherwise, set its frequency to 1
        else
        {
            m[k - i] = m[k - i] + 1;
        }
    }
     
    // Print the result
    cout << result;
}
 
// Driver Code
int main()
{
    vector<int> arr = { 1, 2, 3, 4 };
    int K = 5;
 
    // Function Call
    maxPairs(arr, K);
}
 
// This code is contributed by grand_master

Java

// Java program for the above approach
import java.io.*;
import java.util.*;
 
class GFG {
 
    // Function to find the maximum number
    // of pairs with a sum K such that
    // same element can't be used twice
    public static void maxPairs(
        int[] nums, int k)
    {
 
        // Initialize a hashmap
        Map<Integer, Integer> map
            = new HashMap<>();
 
        // Store the final result
        int result = 0;
 
        // Iterate over the array nums[]
        for (int i : nums) {
 
            // Decrement its frequency
            // in map and increment
            // the result by 1
            if (map.containsKey(i) && 
                map.get(i) > 0) 
            {
 
                map.put(i, map.get(i) - 1);
                result++;
            }
 
            // Increment its frequency by 1
            // if it is already present in map.
            // Otherwise, set its frequency to 1
            else
            {
                map.put(k - i,
                        map.getOrDefault(k - i, 0) + 1);
            }
        }
 
        // Print the result
        System.out.println(result);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int[] arr = { 1, 2, 3, 4 };
        int K = 5;
 
        // Function Call
        maxPairs(arr, K);
    }
}

Python3

# Python3 program for the above approach
 
# Function to find the maximum number
# of pairs with a sum K such that
# same element can't be used twice
def maxPairs(nums, k) :
     
    # Initialize a hashm
    m = {}
     
    # Store the final result
    result = 0
 
    # Iterate over the array nums[]
    for i in nums :
         
        # Decrement its frequency
        # in m and increment
        # the result by 1
        if ((i in m) and m[i] > 0) :        
            m[i] = m[i] - 1
            result += 1
 
        # Increment its frequency by 1
        # if it is already present in m.
        # Otherwise, set its frequency to 1
        else :
         
            if k - i in m :
                m[k - i] += 1
            else :
                m[k - i] = 1
     
    # Print the result
    print(result)
 
# Driver code    
arr = [ 1, 2, 3, 4 ]
K = 5
 
# Function Call
maxPairs(arr, K)
 
# This code is contributed by divyesh072019

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG 
{
 
    // Function to find the maximum number
    // of pairs with a sum K such that
    // same element can't be used twice
    public static void maxPairs(
        int[] nums, int k)
    {
 
        // Initialize a hashmap
        Dictionary<int, int> map
            = new Dictionary<int, int>();
 
        // Store the readonly result
        int result = 0;
 
        // Iterate over the array nums[]
        foreach (int i in nums) 
        {
 
            // Decrement its frequency
            // in map and increment
            // the result by 1
            if (map.ContainsKey(i) &&
                map[i] > 0) 
            {
 
                map[i] = map[i] - 1;
                result++;
            }
 
            // Increment its frequency by 1
            // if it is already present in map.
            // Otherwise, set its frequency to 1
            else
            {
              if (!map.ContainsKey(k - i))
                  map.Add(k - i, 1);
              else
                  map[i] = map[i] + 1;
            }
        }
 
        // Print the result
        Console.WriteLine(result);
    }
 
    // Driver Code
    public static void Main(String[] args)
    {
        int[] arr = {1, 2, 3, 4};
        int K = 5;
 
        // Function Call
        maxPairs(arr, K);
    }
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
// Javascript program for the above approach
 
// Function to find the maximum number
// of pairs with a sum K such that
// same element can't be used twice
function maxPairs(nums, k)
{
     
    // Initialize a hashm
    var m = new Map();
     
    // Store the final result
    var result = 0;
 
    // Iterate over the array nums[]
    nums.forEach(i => {
         
         
        // Decrement its frequency
        // in m and increment
        // the result by 1
        if (m.has(i) && m.get(i) > 0)
        {
            m.set(i, m.get(i)-1);
            result++;
        }
 
        // Increment its frequency by 1
        // if it is already present in m.
        // Otherwise, set its frequency to 1
        else
        {
            if(m.has(k-i))
                m.set(k-i, m.get(k-i)+1)
            else
                m.set(k-i, 1)
        }
    });
     
    // Print the result
    document.write( result);
}
 
// Driver Code
var arr = [1, 2, 3, 4];
var K = 5;
// Function Call
maxPairs(arr, K);
 
</script>

Output:

Time Complexity: O(N)
Auxiliary Space: O(N)

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 zambiatek!