Question
Problem Description You are given a sorted array you need to remove duplicates such that: The first number that occurs more than once is kept
Problem Description You are given a sorted array you need to remove duplicates such that: The first number that occurs more than once is kept one time. The first number that occurs more than twice is kept two times. The first number that occurs more than thrice is kept three times and so on. The above pattern continues until we encounter the first number that occurs more than K or more( i.e. K+1, K+2, and so on) number of times. In these cases, it is kepts K times As you can see the max number of duplicates you would keep for any number is K Input format The first line contains integers N and K, where N and K are the length of the array and the maximum number of duplicates for any number. The second line consists of N space integers numbers which make the input array. Output format The first line is the length of the output array (the array without duplicates) The second line contains the elements of the output array in a space separated manner. Sample Input 1 16 3 1 2 3 3 4 5 5 5 5 6 6 7 7 7 7 7 Sample Output 1 11 1 2 3 4 5 5 6 6 7 7 7 Explanation 1 The number 1 and 2 occur only once and stay intact. The number 3 is the first number to occur more than once and is replaced by one 3. The number 5 is the first number to occur more than twice and is replaced by two 5. This continues for the whole array. Sample Input 2 16 2 1 2 3 3 4 5 5 5 5 6 6 7 7 7 7 7 Sample Output 2 10 1 2 3 4 5 5 6 6 7 7 Constraints N <= 25 * 10^5 1 <= K <= N
java
Code Template:
import java.util.ArrayList;
import java.util.Scanner;
import java.util.HashMap;
public class RetainingRepetitions {
ArrayList
code goes here
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int k = scanner.nextInt();
int arr[] = new int[n];
for(int i = 0 ; i < n ; i++) {
arr[i] = scanner.nextInt();
}
ArrayList
System.out.println(result.size());
for(int i = 0 ; i < result.size() ; i++) {
System.out.print(result.get(i) + " ");
}
scanner.close();
}
}
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started