Given an array arr[] consisting of N positive integers and an integer K, the task is to check if it is possible to reduce the size of the array to at most K or not by removing a subset of the distinct array elements. If it is possible, then print “Yes”. Otherwise, print “No”.
Examples:
Input: arr[] = {2, 2, 2, 3}, K = 3
Output: Yes
Explanation:
By removing the subset {2, 3}, the array modifies to {2, 2} (Size = 2).Input: arr[] = {1, 1, 1, 3}, K = 1
Output: No
Approach: The given problem can be solved by finding the number of distinct elements in the given array, say count. If the value of (N – count) is at most K, then print Yes. Otherwise, print No.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to check if it is possible// to reduce the size of the array to K// by removing the set of the distinct// array elementsvoid maxCount(int arr[], int N, int K){ // Stores all distinct elements // present in the array arr[] set<int> st; // Traverse the given array for (int i = 0; i < N; i++) { // Insert array elements // into the set st.insert(arr[i]); } // Condition for reducing size // of the array to at most K if (N - st.size() <= K) { cout << "Yes"; } else cout << "No";}// Driver Codeint main(){ int arr[] = { 2, 2, 2, 3 }; int K = 3; int N = sizeof(arr) / sizeof(arr[0]); maxCount(arr, N, K); return 0;} |
Java
// Java program for the above approachimport java.util.HashSet;public class GFG{ // Function to check if it is possible // to reduce the size of the array to K // by removing the set of the distinct // array elements static void maxCount(int arr[], int N, int K) { // Stores all distinct elements // present in the array arr[] HashSet<Integer> st = new HashSet<>(); // Traverse the given array for (int i = 0; i < N; i++) { // Insert array elements // into the set st.add(arr[i]); } // Condition for reducing size // of the array to at most K if (N - st.size() <= K) { System.out.println("Yes"); } else System.out.println("No"); } // Driver code public static void main(String[] args) { int arr[] = { 2, 2, 2, 3 }; int K = 3; int N = arr.length; maxCount(arr, N, K); }}// This code is contributed by abhinavjain194 |
Python3
# Python 3 program for the above approach# Function to check if it is possible# to reduce the size of the array to K# by removing the set of the distinct# array elementsdef maxCount(arr, N, K): # Stores all distinct elements # present in the array arr[] st = set() # Traverse the given array for i in range(N): # Insert array elements # into the set st.add(arr[i]) # Condition for reducing size # of the array to at most K if (N - len(st) <= K): print("Yes") else: print("No")# Driver Codeif __name__ == '__main__': arr = [2, 2, 2, 3] K = 3 N = len(arr) maxCount(arr, N, K) # This code is contributed by bgangwar59. |
C#
// C# program for the above approachusing System;using System.Collections.Generic; class GFG{// Function to check if it is possible// to reduce the size of the array to K// by removing the set of the distinct// array elementsstatic void maxCount(int[] arr, int N, int K){ // Stores all distinct elements // present in the array arr[] HashSet<int> st = new HashSet<int>(); // Traverse the given array for(int i = 0; i < N; i++) { // Insert array elements // into the set st.Add(arr[i]); } // Condition for reducing size // of the array to at most K if (N - st.Count <= K) { Console.Write("Yes"); } else Console.Write("No");}// Driver codestatic public void Main(){ int[] arr = { 2, 2, 2, 3 }; int K = 3; int N = arr.Length; maxCount(arr, N, K);}}// This code is contributed by offbeat |
Javascript
<script>// JavaScript program for the above approach// Function to check if it is possible// to reduce the size of the array to K// by removing the set of the distinct// array elementsfunction maxCount(arr, N, K) { // Stores all distinct elements // present in the array arr[] let st = new Set(); // Traverse the given array for (let i = 0; i < N; i++) { // Insert array elements // into the set st.add(arr[i]); } // Condition for reducing size // of the array to at most K if (N - st.size <= K) { document.write("Yes"); } else document.write("No");}// Driver Codelet arr = [2, 2, 2, 3];let K = 3;let N = arr.lengthmaxCount(arr, N, K);</script> |
Output:
Yes
Time Complexity: O(N * log 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
