Page Contents
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!!
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
- Longest AND Subarray
- MEX-OR
- Digit Removal
- Yet another MEX problem
- Characteristic Polynomial Verification
- Chef at the Olympics
- Which Mixture
- Three Boxes