Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# DIGIT GAME

Last Updated on March 28, 2022 by Ria Pathak

### CONCEPTS USED:

Greedy algorithm.

### 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.

1. Run a loop m times.

2. In each iteration, store the maximum number obtained by removing every digit from the current value of n.

3. Consider this maximum as the current value of n and proceed to the next iteration and repeat the above step.

4. 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++){
}
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