Day 24 | Minimum Varied Number | C++

Minimum Varied Number is a fun greedy problem.

Some observations

• We can use each digit once and we need the smallest possible number.

• To reduce the number overall, we need to reduce the total number of digits as well

To solve the problem with the minimum number of digits, we can select the biggest digit available which does not increase the sum > s and include it

The idea is just like this - If you want to travel the distance in the smallest number of steps, you need to take the biggest step possible and keep repeating that till you reach your destination.

Once we have the digits which make sum = s, we need to print it is ascending order to make the overall number the smallest.

You can implement it like this

    set<int> available_digits;
    set<int> ans;
    for(int i = 1; i <= 9; i++)available_digits.insert(i);
    while(s > 0){
        auto it = available_digits.upper_bound(s);
        it = prev(it); // it is upper bound
        s-=*it;
        ans.insert(*it);
        available_digits.erase(it);
    }
    for(auto i: ans)cout << i ;
    cout << '\n';

You can find my implementation here - Submission