CONCEPTS USED:
Greedy algorithm.
DIFFICULTY LEVEL:
PROBLEM STATEMENT(SIMPLIFIED):
Arnab is playing a game. He is given a number N in string format and now he is asked to remove M digits from the number as a part of the game. He wants to return with the maximum value of N possible(Order of digits should not change). Print the maximum value of N.
See original problem statement here
For Example :
1
421 1
If we remove 4 ,the number obtained is 21.
If we remove 2,we get 41.
Removing 1 gives 42.
maximum of 21 ,41 and 42 is 42.OBSERVATION:
To get the maximum possible number after removing m digits, we shall remove m lowest digits.
SOLVING APPROACH:
This problem demands greedy approach.
Iterating m times and removing each digit one by one to get the maximum number for each m is basically what is required to solve the problem.
Run a loop m times.
In each iteration, store the maximum number obtained by removing every digit from the current value of n.
Consider this maximum as the current value of n and proceed to the next iteration and repeat the above step.
The maximum of all these values, is the solution.
SOLUTIONS:
#include<bits/stdc++.h>
using namespace std;
vector<int> num;
int main()
{
int t,n,m,count,a,b;
scanf("%d",&t);
string str;
for(int c=1; c<=t; c++)
{
cin>>str;
cin>>m;
n=str.length();
for(int i=0; i<n; i++)
num.push_back((int)str[i]-48);
count=0;
while(count<m)
{
for(int i=0; i<num.size()-1; i++)
{
if(num[i]<num[i+1])
{
num.erase(num.begin()+i);
count++;
break;
}
else if((i+1==num.size()-1) && num[i]>=num[i+1])
{
num.erase(num.begin()+i+1);
count++;
break;
}
}
}
for(int i=0; i<num.size(); i++)
printf("%d",num[i]);
printf("\n");
num.clear();
}
}
import java.util.*;
import java.util.Scanner;
class HelloWorld{
Vector num = new Vector();
public static void main(String []args){
Scanner myObj = new Scanner(System.in);
HelloWorld h = new HelloWorld();
int t,n,m,count,a,b;
t=Integer.parseInt(myObj.nextLine());
String str;
for(int c=1;c<=t;c++){
str=myObj.nextLine();
m=Integer.parseInt(myObj.nextLine());
n=str.length();
for(int i=0;i<n; i++){
h.num.add(str.charAt(i)-'0');
}
count=0;
while(count<m){
for(int i=0;i<h.num.size()-1;i++){
if((int)h.num.get(i)<(int)h.num.get(i+1)){
h.num.remove(i);
count++;
break;
}
else if((i+1==h.num.size()-1) && (int)h.num.get(i)>=(int)h.num.get(i+1)){
h.num.remove(i+1);
count++;
break;
}
}
}
for(int i=0; i<h.num.size(); i++){
System.out.print(h.num.get(i));
}
System.out.println();
h.num.clear();
}
}
}
[forminator_quiz id="1408"]
This article tried to discuss the concept of Greedy algorithm. Hope this blog helps you understand the concept of Greedy algorithm. To practice more problems you can check out MYCODE|competitive programming