Dev Skill: Game of MODs

Problem link: Game of MODs

In this problem, we are given an integer n with q queries. Each query we have k integer. We need to calculate the maximum and minimum number can be formed after removing k digits from n. Here the digits won't change their position.

Solution: Some things to observer first.

• If k == size of n (digits), then the answer would be 0 0
• If there are leading zeros, we need to remove them, say we got a number like 000000009. this should be changed to 9.
• If we have only 0 digit, then the answer would be zero

We will use recursion technique for building up our desired result. The idea is that a character among first (k+1) characters must be present in the resultant number. So we pick the first (k+1) smallest or largest depending on the situation. Put it on the result, then recur for remaining characters.
This is done in the legend function below. I used a counter variable for checking whether we are creating maximum or minimum number. Look at line 18 for understanding. Only the change in the index can produce two defferent result. Complexity is O(n), the number of digits. Considering all the cases, queries, complexity would be 100*200*11 = 220000

	#include <bits/stdc++.h>
	using namespace std;
	void legend(string s, int n, int counter, string &res)
	{
	if (n == 0)
	{
	res.append(s);
	return;
	}
	int len = s.length();
	if (len <= n)
	return;
	int minIndex = 0;
	for (int i = 1; i<=n ; i++)
	{
	if(counter == 0) // for minimum number
	{
	if (s[i] < s[minIndex])
	minIndex = i;
	}
	else
	{
	if (s[i] > s[minIndex])
	minIndex = i;
	}
	}
	res.push_back(s[minIndex]);
	string new_str = s.substr(minIndex+1, len-minIndex);
	legend(new_str, n-minIndex, counter, res);
	}
	string getNumber(string s, int n, int counter)
	{
	string res = "", x = "";
	legend(s, n, counter, res);
	int len = res.size();
	int flag = 0;
	for(int i = 0; i < len; i++) // removing leading zeros
	{
	if(flag == 0 && res[i] == '0')continue;
	else flag = 1;
	if(flag == 1)x += res[i];
	}
	if(x.size() == 0)x += '0';
	return x;
	}
	int main()
	{
	int t;
	cin>>t;
	for(int tc = 1; tc <= t; tc++)
	{
	string s;
	int k, q;
	cin >> s >> q;
	cout << "Case " << tc << ":" << endl;
	while(q--)
	{
	cin >> k;
	if(k == s.size())
	cout << "0 0" << endl;
	else
	cout << getNumber(s,k,1) << " " << getNumber(s,k,0) << endl;
	}
	}
	return 0;
	}

view raw devskill_GameofMODs.cpp hosted with ❤ by GitHub