October Long Challenge Digit Removal DIGITREM

October Long Challenge Digit Removal DIGITREM

You are given an integer NN and a digit DD. Find the minimum integer you should add to NN such that the final value of NN does not contain the digit DD.

Input Format

  • The first line contains TT denoting the number of test cases. Then the test cases follow.
  • Each test case contains two integers NN and DD on a single line denoting the original number and the digit you need to avoid.

Output Format

For each test case, output on a single line the minimum integer you should add to NN.

Constraints

  • 1≤T≤1051≤T≤105
  • 1≤N≤1091≤N≤109
  • 0≤D≤90≤D≤9

Subtasks

  • Subtask 1 (100 points): Original constraints

Sample Input 1 

5
21 5
8 8
100 0
5925 9
434356 3

Sample Output 1 

0
1
11
75
5644

Explanation

Test case 11: N=21N=21 does not contain the digit D=5D=5. Hence there is no need to add any integers to NN.

Test case 22: If 11 is added to N=8N=8, it becomes equal to 99, which does not contain the digit D=8D=8.

Test case 33: The minimum integer you should add to N=100N=100 such that the final value of NN does not contain the digit D=0D=0 is 1111.

Test case 55: The minimum integer which is greater than 434356434356 and does not contain the digit D=3D=3 is 440000440000. So we should add 440000−434356=5644440000−434356=5644.

CLICK BELOW!!

Digit Removal DIGITREM
Digit Removal DIGITREM

Solution

Program C++:

#include <bits/stdc++.h>
using namespace std;

#define tc ll t sc cin >> t sc while (t--)
#define ff first
#define sc ;
#define ss second
#define pb push_back
#define pp pop_back
#define mp make_pair
#define ll long long
#define Radhe ios::sync_with_stdio(false);
#define Krishna cin.tie(NULL);

int main()
{
    tc
    {
        ll n;
        ll d;

        cin >> n;
        cin >> d;

        string str = to_string(n);
        ll len = str.length();

        if (d == 0)
        {
            int ind2=len;
            
            for (int i = 0; i < len; i++)
            {
                if (str[i] == '0')
                {
                    str[i] = '1';
                    ind2=i;
                    break;
                }
            }

            for (int j = ind2 + 1; j < len; j++)
            {
                str[j] = '1';
            }
        }
        else if (d == 9)
        {
            if (str[0] == '9')
            {
                for (int i = 0; i < len; i++)
                {
                    str[i] = '0';
                }
                str = "1" + str;
            }
            else
            {
                int ind=len;
                for (int i = 0; i < len; i++)
                {
                    if (str[i] == '9')
                    {
                        
                        for(int k=i-1; k >= 0; k--)
                        {
                            if(str[k] <= '7')
                            {
                                str[k]++;
                                ind=k;
                                goto cvv;
                            }
                        }
                        
                        for (int i = 0; i < len; i++)
                        {
                            str[i] = '0';
                        }
                        str = "1" + str;
                        
                        goto fvv;
                    }
                }
                
                
                
                
                cvv:;

                for (int j = ind+1; j < len; j++)
                {
                    str[j] = '0';
                }
                
                fvv:;
            }
        }
        else
        {
            int i = 0;
            for (i = 0; i < len; i++)
            {
                if ((str[i] - 48) == d)
                {
                    str[i]=str[i]+1;
                    break;
                }
            }

            for (int j = i + 1; j < len; j++)
            {
                str[j] = '0';
            }
        }

        ll nn = stoll(str);

        cout << nn - n << "\n";
    }
}

October Long Challenge 2021

Leave a Comment