Given an array arr[] and an integer N, the task is to find the maximum number of pairs that can be formed such that ith index is included in almost arr[i] pairs.
Examples:
Input: arr[] = {2, 2, 3, 4}
Output:
5
1 3
2 4
2 4
3 4
3 4
Explanation: For the given array, a maximum of 5 pairs can be created where 1st index is included in 1 pair, 2nd index in 2 pairs, 3rd index in 3 pairs and 4th index in 4 pairs as shown above.Input: arr[] = {8, 2, 0, 1, 1}
Output:
4
1 2
1 5
1 4
1 2
Approach: The given problem can be solved using a greedy approach. It can be observed that the most optimal choice at every step is to choose the elements with the maximum value and create their respective pair. Using this observation, follow the below steps to solve this problem:
- Create a Max Priority Queue which stores the indices of the given array in decreasing order of their respective array value.
- Create a loop to iterate the priority queue until there are more than two elements in it and follow the below steps:
- Print all the pairs in the answer array.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;void maxPairs(int arr[], int n){ // Stores the final list // of pairs required vector<int> matchList; // Max Priority Queue to // store induced in order // of their array value priority_queue<int> pq; // Loop to iterate arr[] for (int i = 0; i < n; i++) { if (arr[i] > 0) pq.push(i); } // Loop to iterate pq // till it has more // than 2 elements while (pq.size() >= 2) { // Stores the maximum int top = pq.top(); pq.pop(); // Stores the second // maximum int cur = pq.top(); pq.pop(); // Insert pair into the // final list matchList.push_back(top + 1); matchList.push_back(cur + 1); arr[top]--; arr[cur]--; if (arr[top] > 0) pq.push(top); if (arr[cur] > 0) pq.push(cur); } // Print Answer cout << (matchList.size() / 2) << "\n"; for (int i = 0; i < matchList.size(); i += 2) { cout << matchList[i] << " " << matchList[i+1] << "\n"; }} // Driver codeint main(){ int arr[] = { 1, 2, 3, 4 }; int n = sizeof(arr)/sizeof(arr[0]); maxPairs(arr,n); return 0;}// This code is contributed by Aditya Patil |
Java
// Java implementation of above approachimport java.io.*;import java.util.*;class GFG { public static void maxPairs(int arr[]) { // Stores the final list // of pairs required List<Integer> matchList = new ArrayList<>(); // Max Priority Queue to // store induced in order // of their array value PriorityQueue<Integer> pq = new PriorityQueue<>( (x, y) -> arr[y] - arr[x]); // Loop to iterate arr[] for (int i = 0; i < arr.length; i++) { if (arr[i] > 0) pq.add(i); } // Loop to iterate pq // till it has more // than 2 elements while (pq.size() >= 2) { // Stores the maximum int top = pq.poll(); // Stores the second // maximum int cur = pq.poll(); // Insert pair into the // final list matchList.add(top + 1); matchList.add(cur + 1); arr[top]--; arr[cur]--; if (arr[top] > 0) pq.add(top); if (arr[cur] > 0) pq.add(cur); } // Print Answer System.out.println(matchList.size() / 2); for (int i = 0; i < matchList.size(); i += 2) { System.out.println(matchList.get(i) + " " + matchList.get(i + 1)); } } // Driver code public static void main(String[] args) { int arr[] = { 1, 2, 3, 4 }; maxPairs(arr); }} |
Python3
# Python implementation of the approachimport bisectdef maxPairs(arr,n): # Stores the final list # of pairs required matchList=[] # Max Priority Queue to # store induced in order # of their array value pq=[] #Loop to iterate arr[] for i in range(n): if(arr[i]>0): bisect.insort(pq,i) # Loop to iterate pq # till it has more # than 2 elements while(len(pq)>=2): # Stores the maximum top=pq[-1] pq.pop(-1) # Stores the second cur=pq[-1] pq.pop(-1) # Insert pair into the # final list matchList.append(top+1) matchList.append(cur+1) arr[top]=arr[top]-1 arr[cur]=arr[cur]-1 if(arr[top]>0): bisect.insort(pq,top) if(arr[cur]>0): bisect.insort(pq,cur) # Print Answer print(len(matchList)//2) for i in range(0,len(matchList),2): print(matchList[i],end=" ") print(matchList[i+1]) # Driver codearr=[1,2,3,4]n=len(arr)maxPairs(arr,n)# This code is contributed by Pushpesh Raj. |
C#
using System;using System.Collections;using System.Collections.Generic;using System.Linq;class HelloWorld { // Custom sort function. class GFG : IComparer<int> { public int Compare(int x, int y) { // "CompareTo()" method return y.CompareTo(x); } } public static void maxPairs(int[] arr, int n) { // Stores the final list // of pairs required List<int> matchList = new List<int>();; // Max Priority Queue to // store induced in order // of their array value List<int> pq = new List<int>(); // Loop to iterate arr[] for (int i = 0; i < n; i++) { if (arr[i] > 0) pq.Add(i); } // Loop to iterate pq // till it has more // than 2 elements // Sort it. GFG gg = new GFG(); pq.Sort(gg); while (pq.Count >= 2) { // Stores the maximum int top = pq.First(); pq.RemoveAt(0); // Stores the second // maximum int cur = pq.First(); pq.RemoveAt(0); // Insert pair into the // final list matchList.Add(top + 1); matchList.Add(cur + 1); arr[top]--; arr[cur]--; if (arr[top] > 0){ pq.Add(top); pq.Sort(gg); } if (arr[cur] > 0){ pq.Add(cur); pq.Sort(gg); } } // Print Answer Console.WriteLine(matchList.Count / 2); for (int i = 0; i < matchList.Count; i += 2) { Console.WriteLine(matchList[i] + " " + matchList[i+1]); } } // Driver Code. static void Main() { int[] arr = { 1, 2, 3, 4 }; int n = arr.Length; maxPairs(arr,n); }}// The code is contributed by Arushi Jindal. |
Javascript
// JavaScript implementation of the approachfunction maxPairs(arr, n) { // Stores the final list // of pairs required let matchList = []; // Max Priority Queue to // store induced in order // of their array value let pq = []; // Loop to iterate arr[] for (let i = 0; i < n; i++) { if (arr[i] > 0) { pq.push(i); pq.sort(); } } // Loop to iterate pq // till it has more // than 2 elements while (pq.length >= 2) { // Stores the maximum let top = pq.pop(); // Stores the second let cur = pq.pop(); // Insert pair into the // final list matchList.push(top + 1); matchList.push(cur + 1); arr[top] = arr[top] - 1; arr[cur] = arr[cur] - 1; if (arr[top] > 0) { pq.push(top); pq.sort(); } if (arr[cur] > 0) { pq.push(cur); pq.sort(); } } // Print Answer console.log(matchList.length / 2); for (let i = 0; i < matchList.length; i += 2) { console.log(matchList[i], matchList[i + 1]); }}// Driver codelet arr = [1, 2, 3, 4];let n = arr.length;maxPairs(arr, n);// This code is contributed by vinayetbi1. |
Output
5 4 3 4 3 4 3 4 2 2 1
Time Complexity: O(M*log M), where M denotes the sum of all array elements
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
