lowest_number_erase_k_digit.cpp

/*

Introduction to algorithms is considered as easiest subject
among the students of firstyears, so they are not focusing
much on lectures. when professor realises this he becomesvery
angry and plans to fail all the students of the batch. He writes a
very big number on thewhiteboard and says : "This will be the
minimum mark required to pass this course" . Whenstudents
see this gigantic number written on the whiteboard most of
them become prettysure that they are going to fail this
semester. So the some of the students started trying
toconvince the professor to not do so. So the professor gives
them a number K and says : "Youcan erase exactly K digits of
the given number". Now students want to make this number
assmall as possible. So you being the second most intelligent
student of the batch decide tosolve the problem. Save the
other students.

*/

#include <iostream>
#include <string>
#include <algorithm>
std::string lowest_number(std::string str, int k)
{
    std::string res = "";
    if (k == 0)
    {
        res.append(str);
        return res;
    }
    if (str.length() <= k)
        return res;
    int min = 0;
    for (int i = 1; i <= k; i++)
        if (str[i] < str[min])
            min = i;
    res += str[min];

    return res + lowest_number(str.substr(min + 1), k - min);
}

int main()
{
    std::string str = "412199", res = "";
    int k = 2;
    res = lowest_number(str, k);
    size_t pos = 0;
    for (size_t i = 0; i < res.length(); i++)
    {
        if (res[i] == '0')
            pos++;
        else
            break;
    }
    res.erase(0, pos);
    std::cout << res;
    return 0;
}