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.

  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++){
                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

Leave a Reply

Your email address will not be published. Required fields are marked *