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 by referring data structures and algorithms tutorials.

  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();
        }
    }
    }

Previous post BLOCK MOVE
Next post FRACTION

Leave a Reply

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