Given a sorted array arr of size N, the task is to reduce the array such that each element can appear at most K times.
Examples:
Input: arr[] = {1, 2, 2, 2, 3}, K = 2
Output: {1, 2, 2, 3}
Explanation:
Remove 2 once, as it occurs more than 2 times.
Input: arr[] = {3, 3, 3}, K = 1
Output: {3}
Explanation:
Remove 3 twice, as it occurs more than 1 times.
Approach:
- Traverse the given array arr
- Maintain the count of each unique element in the array while traversing, using a pointer i
- If the current frequency of arr[i] till index i is less than or equal to K, add the element arr[i] to the new reduced array and increment the frequency by 1.
- If the current frequency of arr[i] till index i is more than K, skip till you find the next unique element.
- After the traversal ends, print the reduced array.
Below is the implementation of the above approach:
C++
// C++ program to reduce the array// such that each element appears// at most K times#include <bits/stdc++.h>using namespace std;// Function to reduce the arrayvoid reduceArray(int arr[], int n, int K){ // Vector to store the reduced array vector<int> vec; int size = 0; int curr_ele = arr[0], curr_freq = 1; // Iterate over the array for (int i = 0; i < n; i++) { if (curr_ele == arr[i] && curr_freq <= K) { vec.push_back(arr[i]); size++; } else if (curr_ele != arr[i]) { curr_ele = arr[i]; vec.push_back(arr[i]); size++; curr_freq = 1; } curr_freq++; } // Print the reduced array cout << "{"; for (int i = 0; i < size; i++) { cout << vec[i] << ", "; } cout << "}";}// Driver codeint main(){ int arr[] = { 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 5 }; int n = sizeof(arr) / sizeof(arr[0]); int K = 2; // Function call reduceArray(arr, n, K); return 0;} |
Java
// Java program to reduce the array// such that each element appears// at most K timesimport java.util.*;class GFG{ // Function to reduce the arraystatic void reduceArray(int arr[], int n, int K){ // Vector to store the reduced array Vector<Integer> vec = new Vector<Integer>(); int size = 0; int curr_ele = arr[0], curr_freq = 1; // Iterate over the array for (int i = 0; i < n; i++) { if (curr_ele == arr[i] && curr_freq <= K) { vec.add(arr[i]); size++; } else if (curr_ele != arr[i]) { curr_ele = arr[i]; vec.add(arr[i]); size++; curr_freq = 1; } curr_freq++; } // Print the reduced array System.out.print("{"); for (int i = 0; i < size; i++) { System.out.print(vec.get(i)+ ", "); } System.out.print("}");} // Driver codepublic static void main(String[] args){ int arr[] = { 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 5 }; int n = arr.length; int K = 2; // Function call reduceArray(arr, n, K); }}// This code is contributed by PrinciRaj1992 |
Python3
# Python3 program to reduce the array# such that each element appears# at most K times# Function to reduce the arraydef reduceArray(arr, n, K) : # List to store the reduced array vec = []; size = 0; curr_ele = arr[0]; curr_freq = 1; # Iterate over the array for i in range(n) : if (curr_ele == arr[i] and curr_freq <= K) : vec.append(arr[i]); size += 1; elif (curr_ele != arr[i]) : curr_ele = arr[i]; vec.append(arr[i]); size += 1; curr_freq = 1; curr_freq += 1; # Print the reduced array print("{",end= ""); for i in range(size) : print(vec[i] ,end= ", "); print("}",end="");# Driver codeif __name__ == "__main__" : arr = [ 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 5 ]; n = len(arr) K = 2; # Function call reduceArray(arr, n, K);# This code is contributed by AnkitRai01 |
C#
// C# program to reduce the array// such that each element appears// at most K timesusing System;using System.Collections.Generic;class GFG{ // Function to reduce the arraystatic void reduceArray(int []arr, int n, int K){ // List to store the reduced array List<int> vec = new List<int>(); int size = 0; int curr_ele = arr[0], curr_freq = 1; // Iterate over the array for (int i = 0; i < n; i++) { if (curr_ele == arr[i] && curr_freq <= K) { vec.Add(arr[i]); size++; } else if (curr_ele != arr[i]) { curr_ele = arr[i]; vec.Add(arr[i]); size++; curr_freq = 1; } curr_freq++; } // Print the reduced array Console.Write("{"); for (int i = 0; i < size; i++) { Console.Write(vec[i]+ ", "); } Console.Write("}");} // Driver codepublic static void Main(String[] args){ int []arr = { 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 5 }; int n = arr.Length; int K = 2; // Function call reduceArray(arr, n, K);}}// This code is contributed by Princi Singh |
Javascript
<script>// JavaScript program to reduce the array// such that each element appears// at most K times// Function to reduce the arrayfunction reduceArray( arr, n, K){ // Vector to store the reduced array var vec=[]; var size = 0; var curr_ele = arr[0], curr_freq = 1; // Iterate over the array for (var i = 0; i < n; i++) { if (curr_ele == arr[i] && curr_freq <= K) { vec.push(arr[i]); size++; } else if (curr_ele != arr[i]) { curr_ele = arr[i]; vec.push(arr[i]); size++; curr_freq = 1; } curr_freq++; } // Print the reduced array document.write( "{"); for (var i = 0; i < size; i++) { document.write( vec[i] +", "); } document.write("}");}var arr = [ 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 5 ]; var n = 14; var K = 2; // Function call reduceArray(arr, n, K);</script> |
Output
{1, 1, 2, 2, 3, 3, 4, 5, }
Time complexity: O(N)
Auxiliary Space: O(N), where N is the size of the given array.
Efficient Approach:-
- As the array is sorted so the same type of elements are present adjacent to each other
- We will simply traverse the array and only print a element at most K times
Implementation:-
C++
// C++ program to reduce the array// such that each element appears// at most K times#include <bits/stdc++.h>using namespace std;// Function to reduce the arrayvoid reduceArray(int arr[], int n, int K){ // count of current element int c = 0; // current element int curr = arr[0]; // Iterate over the array for (int i = 0; i < n; i++) { // if same element increase count if (arr[i] == curr) c++; // else make count 1 and change current element else { c = 1; curr = arr[i]; } // if count is less than K print the element if (c <= K) cout << arr[i] << " "; }}// Driver codeint main(){ int arr[] = { 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 5 }; int n = sizeof(arr) / sizeof(arr[0]); int K = 2; // Function call reduceArray(arr, n, K); return 0;}// This code is contributed by shubhamrajput6156 |
Java
// Java program to reduce the array// such that each element appears// at most K timesimport java.util.Scanner;class Main { // Function to reduce the array public static void reduceArray(int arr[], int n, int K) { // count of current element int c = 0; // current element int curr = arr[0]; // Iterate over the array for (int i = 0; i < n; i++) { // if same element increase count if (arr[i] == curr) c++; // else make count 1 and change current element else { c = 1; curr = arr[i]; } // if count is less than K print the element if (c <= K) System.out.print(arr[i] + " "); } } // Driver code public static void main(String args[]) { int arr[] = { 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 5 }; int n = arr.length; int K = 2; // Function call reduceArray(arr, n, K); }} |
Python3
# Python program to reduce the array# such that each element appears# at most K times# Function to reduce the arraydef reduce_array(arr, n, K): # count of current element c = 0 # current element curr = arr[0] for i in range(n): # if same element increase count if arr[i] == curr: c += 1 # else make count 1 and change current element else: c = 1 curr = arr[i] # if count is less than K print the element if c <= K: print(arr[i], end=' ')# driver codearr = [1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 5]n = len(arr)K = 2reduce_array(arr, n, K)# This code is contributed by redmoonz. |
C#
// C# program to reduce the array// such that each element appears// at most K timesusing System;public static class Globals{ // Function to reduce the array public static void reduceArray(int[] arr, int n, int K) { // count of current element int c = 0; // current element int curr = arr[0]; // Iterate over the array for (int i = 0; i < n; i++) { // if same element increase count if (arr[i] == curr) c++; // else make count 1 and change current element else{ c = 1; curr = arr[i]; } // if count is less than K print the element if (c <= K) { Console.Write(" "); Console.Write(arr[i]); } } } // Driver Code internal static void Main() { int[] arr = {1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 5}; int n = arr.Length; int K = 2; // Function call reduceArray(arr, n, K); }}// This code is contributed by bhardwajji |
Javascript
// Function to reduce the arrayfunction reduceArray(arr, n, K) { // count of current element let c = 0; // current element let curr = arr[0]; let output = ""; // Iterate over the array for (let i = 0; i < n; i++) { // if same element increase count if (arr[i] === curr) c++; // else make count 1 and change current element else { c = 1; curr = arr[i]; } // if count is less than K print the element if (c <= K) output += arr[i] + " "; } console.log(output);}// Driver codeconst arr = [1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 5];const n = arr.length;const K = 2;// Function callreduceArray(arr, n, K); |
Output
1 1 2 2 3 3 4 5
Time Complexity:- O(N)
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!
