Given an array A[] of length N, the task is to find the minimum size of the array after selecting and removing distinct element pairs any number of times.
Examples:
Input: A[] = {1, 7, 7, 4, 4, 4}, N = 6
Output: 0
Explanation: 3 pairs containing distinct elements can be formed from the array. Thus, no element left in the array.Input: A[] = {25, 25}, N = 2
Output: 2
Explanation: No pairs containing distinct elements can be formed from the array. Thus, 2 elements left in the array.
Solution: Follow the steps below to solve this problem:
- Create a map, say mp to store the frequency of each element in the array. Let the maximum frequency of any element be m.
- If the length of the array is even:
- Notice that if m is less than or equal to (N/2), then every element can form a pair with another. Thus, output 0.
- Otherwise, the minimum size of the array i.e, the number of elements left without a pair are given by:
- If the length of the array is odd:
- Notice that if m is greater than or equal to (N/2), then 1 element will always be left without any pair. Thus, output 1.
- Otherwise, the minimum size of the array will again be given by (2*m–N).
Below is the implementation of the above code:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the minimum size of// of the array after performing a set of// operationsint minSize(int N, int A[]){ // Map to store the frequency of each // element of the array map<int, int> mpp; // Stores the maximum frequency of an // element int m = 0; // Loop to find the maximum frequency of // an element for (int i = 0; i < N; ++i) { // Increment the frequency mpp[A[i]]++; // Stores the maximum frequency m = max(mpp[A[i]], m); } // If N is even if (N % 2 == 0) { // If m is less than or equal to N/2 if (m <= N / 2) { return 0; } else { return (2 * m) - N; } } else { // If m is less than or equal to N/2 if (m <= N / 2) { return 1; } else { return (2 * m) - N; } }}// Driver Codeint main(){ // Given input int N = 6; int A[N] = { 1, 7, 7, 4, 4, 4 }; // Function Call cout << minSize(N, A); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG { // Function to find the minimum size of // of the array after performing a set of // operations static int minSize(int N, int[] A) { // Map to store the frequency of each // element of the array HashMap<Integer, Integer> mpp = new HashMap<Integer, Integer>(); // Stores the maximum frequency of an // element int m = 0; // Loop to find the maximum frequency of // an element for (int i = 0; i < N; ++i) { // Increment the frequency if (mpp.containsKey(A[i])) { mpp.put(A[i], mpp.get(A[i]) + 1); } else { mpp.put(A[i], 1); } // Stores the maximum frequency m = Math.max(mpp.get(A[i]), m); } // If N is even if (N % 2 == 0) { // If m is less than or equal to N/2 if (m <= N / 2) { return 0; } else { return (2 * m) - N; } } else { // If m is less than or equal to N/2 if (m <= N / 2) { return 1; } else { return (2 * m) - N; } } } // Driver Code public static void main(String[] args) { // Given input int N = 6; int[] A = { 1, 7, 7, 4, 4, 4 }; // Function Call System.out.println(minSize(N, A)); }}// This code is contributed by ukasp. |
Python3
# Python program for the above approach# Function to find the minimum size of# of the array after performing a set of# operationsdef minSize(N, A): # Map to store the frequency of each # element of the array mpp = {} # Stores the maximum frequency of an # element m = 0 # Loop to find the maximum frequency of # an element for i in range(N): if A[i] not in mpp: mpp[A[i]]=0 # Increment the frequency mpp[A[i]]+=1 # Stores the maximum frequency m = max(mpp[A[i]], m) # If N is even if (N % 2 == 0): # If m is less than or equal to N/2 if (m <= N / 2): return 0 else: return (2 * m) - N else: # If m is less than or equal to N/2 if (m <= N / 2): return 1 else: return (2 * m) - N # Driver Code# Given inputN = 6A = [1, 7, 7, 4, 4, 4]# Function Callprint(minSize(N, A))# This code is contributed by Shubham Singh |
C#
// C# program for the above approachusing System;using System.Collections;using System.Collections.Generic;class GFG{ // Function to find the minimum size of // of the array after performing a set of // operations static int minSize(int N, int []A) { // Map to store the frequency of each // element of the array Dictionary<int, int> mpp = new Dictionary<int, int>(); // Stores the maximum frequency of an // element int m = 0; // Loop to find the maximum frequency of // an element for (int i = 0; i < N; ++i) { // Increment the frequency if (mpp.ContainsKey(A[i])) { mpp[A[i]] = mpp[A[i]] + 1; } else { mpp.Add(A[i], 1); } // Stores the maximum frequency m = Math.Max(mpp[A[i]], m); } // If N is even if (N % 2 == 0) { // If m is less than or equal to N/2 if (m <= N / 2) { return 0; } else { return (2 * m) - N; } } else { // If m is less than or equal to N/2 if (m <= N / 2) { return 1; } else { return (2 * m) - N; } } } // Driver Code public static void Main() { // Given input int N = 6; int []A = { 1, 7, 7, 4, 4, 4 }; // Function Call Console.Write(minSize(N, A)); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the above approach // Function to find the minimum size of // of the array after performing a set of // operations function minSize(N, A) { // Map to store the frequency of each // element of the array let mpp = new Map(); // Stores the maximum frequency of an // element let m = 0; // Loop to find the maximum frequency of // an element for (let i = 0; i < N; ++i) { // Increment the frequency if (!mpp.has(A[i])) mpp.set(A[i], 1); else mpp.set(A[i], mpp.get(A[i]) + 1) // Stores the maximum frequency m = Math.max(mpp.get(A[i]), m); } // If N is even if (N % 2 == 0) { // If m is less than or equal to N/2 if (m <= Math.floor(N / 2)) { return 0; } else { return (2 * m) - N; } } else { // If m is less than or equal to N/2 if (m <= Math.floor(N / 2)) { return 1; } else { return (2 * m) - N; } } } // Driver Code // Given input let N = 6; let A = [1, 7, 7, 4, 4, 4] // Function Call document.write(minSize(N, A)); // This code is contributed by Potta Lokesh </script> |
Output:
0
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
