DIGITREM - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Practice

Setter: Soumyadeep Pal
Tester: Istvan Nagy
Editorialist: Taranpreet Singh

DIFFICULTY

Easy

PREREQUISITES

Basic Math.

PROBLEM

You are given an integer N and a digit D. Find the minimum non-negetive integer you should add to N such that the final value of N does not contain the digit D.

QUICK EXPLANATION

  • We need to find the smallest integer T \geq N such that D is not present in T. T-N is the required number of operations.
  • Consider digits from right to left. If current digit is D, increase it to D+1 and make all digits to the right equal to 0 (or 1 if D = 0)

EXPLANATION

For now, let’s ignore D = 0 case. Assuming 1 \leq D \leq 9.

Let’s say we get N = 5925 and D = 9. Third digit from the right is equal to D, so we need to change that digit. By adding anything less than 75, that digit remains unchanged.

We can observe that we need to increase 59XX to 60XX where each X may be replaced by any digit. Since we want to minimize T, it’d be optimal to choose T = 6000. The number of operation would be 100-XX, which in above case was 100-25 = 75.

So, we can see that as soon as we get a digit equal to D, we need to increase that by one and make all digits to its right equal to 0.

Now, we can consider digits either from left to right or right to left.

Consider N = 88888889 and D = 9. The smallest T here is 100000000. If we consider digits from left to right, as soon as we hit 9, we would again need to consider all digits to left of 9.

The reason this happened was due to carry forward. It is handled easier when considering digits from right to left, as addition happens from right to left.

Hence, considering digits from right to left, as soon as we hit a digit D, make that digit D+1 (If D = 9, make it 0 and increase digit to its immediate left by 1.

Specifically, starting from T = N, if x-th digit from right (numbered from 0) is equal to D, add 10^x - T \bmod 10^x. When we had N = 5925 and D = 9, we have x = 2, so we add 10^2 - (5925 \bmod 100) = 100-25 = 75 to T. Repeat this process till there’s no occurrence of D in T.

When D = 0

In this case, we cannot make digits to the right 0. So the smallest choice we have is making digits to its right equal to 1.

Let’s say we get N = 5025 and D = 0, the smallest integer T is 5111.

TIME COMPLEXITY

The time complexity is O(log_{10} (N)) per test case.

SOLUTIONS

Setter's Solution
#include<bits/stdc++.h>
using namespace std;
template <class T> ostream &operator << (ostream & os, const vector<T> &p) { os << "["; for (auto&it : p) os << it << " "; return os << "]";}
template <class S, class T> ostream &operator << (ostream & os, const pair<S, T> &p) { return os << "(" << p.first << "," << p.second << ")";}
#ifndef ONLINE_JUDGE
#define deb(...) dbs(#__VA_ARGS__,__VA_ARGS__)
template <class T> void dbs(string str, T t) { cerr << str << ":" << t << "\n";}
template<class T, class...S> void dbs(string str, T t, S... s) { int idx = str.find(','); cerr << str.substr(0, idx) << ":" << t << ","; dbs(str.substr(idx + 1), s...);}
#else
#define deb(...){}
#endif
#define int long long
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define ini(x, y) memset(x, y, sizeof(x))
#define pr(x) {cout << x << '\n'; return;}
#define nl cout<< '\n'
#define rep(i,n) for(int i = 0; i < n; i++)
#define re(i,n) for(int i = 1; i <= n; i++)
#define vi vector<int>
#define pii pair<int, int>
#define vii vector<pii>
template<class T> inline T Bit(T x, int i) { return (x >> i) & 1;}
template<class T> bool umin(T & a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool umax(T & a, T b) { return a < b ? (a = b, true) : false; }
const int N = 1e3 + 3; // check the limits


int greedy(int n, int d) {
  if (n == d) return 1;
  string s = to_string(n);
  int len = sz(s);
  int pos = n;
  int num = 1;
  for (int i = 0; i < len; i++) {
    if (s[i] == '0' + d) {
      if (d == 9 && i >= 1 && s[i - 1] == '8') {
        int p2 = i - 1;
        for (int j = i - 1; j >= 0; j--) {
          if (s[j] == '8') p2 = j;
          else break;
        }
        for (int j = p2; j < len; j++) {
          num *= 10;
        }
        int dig = 0;
        for (int j = p2; j < len; j++) {
          dig = dig * 10 + (s[j] - '0');
        }
        // deb(num, dig);
        return (num - dig);
        break;
      }
      if (d == 0) {
        for (int j = i + 1; j < len; j++) {
          num = num * 10 + 1;
        }
        int dig = 0;
        for (int j = i + 1; j < len; j++) {
          dig = dig * 10 + (s[j] - '0');
        }
        return (num - dig);
      }
      pos = i;
      for (int j = i + 1; j < len; j++) {
        num *= 10;
      }
      int dig = 0;
      for (int j = i + 1; j < len; j++) {
        dig = dig * 10 + (s[j] - '0');
      }
      return (num - dig);
      break;
    }
  }
  return 0;
}



void solve(int tc) {
  int n, d; cin >> n >> d;
  cout << greedy(n, d) << '\n';
}



signed main() {
  ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int t = 1;
  cin >> t;
  for (int i = 1; i <= t; i++) {
    solve(i);
  }
  return 0;
}
Tester's Solution
#include <iostream>
#include <cassert>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <random>

#ifdef HOME
    #include <windows.h>
#endif

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

template<class T> bool umin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool umax(T &a, T b) { return a < b ? (a = b, true) : false; }

using namespace std;

long long readInt(long long l, long long r, char endd) {
    long long x = 0;
    int cnt = 0;
    int fi = -1;
    bool is_neg = false;
    while (true) {
	    char g = getchar();
	    if (g == '-') {
		    assert(fi == -1);
		    is_neg = true;
		    continue;
	    }
	    if ('0' <= g && g <= '9') {
		    x *= 10;
		    x += g - '0';
		    if (cnt == 0) {
			    fi = g - '0';
		    }
		    cnt++;
		    assert(fi != 0 || cnt == 1);
		    assert(fi != 0 || is_neg == false);

		    assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
	    }
	    else if (g == endd) {
		    assert(cnt > 0);
		    if (is_neg) {
			    x = -x;
		    }
		    assert(l <= x && x <= r);
		    return x;
	    }
	    else {
		    //assert(false);
	    }
    }
}

string readString(int l, int r, char endd) {
    string ret = "";
    int cnt = 0;
    while (true) {
	    char g = getchar();
	    assert(g != -1);
	    if (g == endd) {
		    break;
	    }
	    cnt++;
	    ret += g;
    }
    assert(l <= cnt && cnt <= r);
    return ret;
}
long long readIntSp(long long l, long long r) {
    return readInt(l, r, ' ');
}
long long readIntLn(long long l, long long r) {
    return readInt(l, r, '\n');
}
string readStringLn(int l, int r) {
    return readString(l, r, '\n');
}
string readStringSp(int l, int r) {
    return readString(l, r, ' ');
}

vector<int> getDigits(int N)
{
    vector<int> res;
    while (N)
    {
	    res.push_back(N % 10);
	    N /= 10;
    }
    return res;
}

int calcDigits(const vector<int>& v)
{
    int res = 0;
    int mul = 1;
    for (const auto& vi : v)
    {
	    res += vi * mul;
	    mul *= 10;
    }
    return res;
}

int main(int argc, char** argv) 
{
#ifdef HOME
    if(IsDebuggerPresent())
    {
	    freopen("../in.txt", "rb", stdin);
	    freopen("../out.txt", "wb", stdout);
    }
#endif
    int T = readIntLn(1, 100'000);
    vector<int> w(10,1);
    fore(i, 1, w.size() - 1)
    {
	    w[i] = w[i - 1] * 10;
    }

    forn(tc, T)
    {
	    int N = readIntSp(1, 1'000'000'000);
	    int d = readIntLn(0, 9);
	    int NN = N;
	    while (true)
	    {
		    auto nd = getDigits(NN);
		    int fd = -1;
		    forn(i, nd.size())
		    {
			    if (nd[i] == d)
				    fd = i;
		    }
		    if (fd != -1)
		    {
			    forn(i, fd)
			    {
				    nd[i] = d == 0 ? 1 : 0;
			    }
		    }
		    else
			    break;
		    NN = calcDigits(nd);
		    if (fd != -1)
			    NN += w[fd];
	    }
	    printf("%d\n", NN - N);
    }
    assert(getchar() == -1);
    return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class DIGITREM{
    //SOLUTION BEGIN
    Random R = new Random();
    int MX = 10000;
    void pre() throws Exception{}
    void solve(int TC) throws Exception{
        long N = nl(), D = nl();
        pn(fast(N, D)-N);
    }
    long fast(long N, long D){
        long T = N;
        long add0 = 0;
        for(long pw10 = 1; pw10 <= 1000000000000000L; pw10 *= 10){
            if(T/pw10 == 0)break;
            long d = (T/pw10)%10;
            if(d == D){
                long num = (T/pw10+1)*pw10 + (D == 0?add0:0);
                T = num;
            }
            add0 += pw10;
        }
        return T;
    }
    boolean contains(long N, long d){
        
        while(N>0){
            if(N%10 == d)return true;
            N /= 10;
        }
        return false;
    }
    long brute(long N, long D){
        while(contains(N, D))N++;
        return N;
    }
    //SOLUTION END
    void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
    static boolean multipleTC = true;
    FastReader in;PrintWriter out;
    void run() throws Exception{
        in = new FastReader();
        out = new PrintWriter(System.out);
        //Solution Credits: Taranpreet Singh
        int T = (multipleTC)?ni():1;
        pre();for(int t = 1; t<= T; t++)solve(t);
        out.flush();
        out.close();
    }
    public static void main(String[] args) throws Exception{
        new DIGITREM().run();
    }
    int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
    void p(Object o){out.print(o);}
    void pn(Object o){out.println(o);}
    void pni(Object o){out.println(o);out.flush();}
    String n()throws Exception{return in.next();}
    String nln()throws Exception{return in.nextLine();}
    int ni()throws Exception{return Integer.parseInt(in.next());}
    long nl()throws Exception{return Long.parseLong(in.next());}
    double nd()throws Exception{return Double.parseDouble(in.next());}

    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }

        String next() throws Exception{
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    throw new Exception(e.toString());
                }
            }
            return st.nextToken();
        }

        String nextLine() throws Exception{
            String str = "";
            try{   
                str = br.readLine();
            }catch (IOException e){
                throw new Exception(e.toString());
            }  
            return str;
        }
    }
}

Feel free to share your approach. Suggestions are welcomed as always. :slight_smile:

2 Likes

I was trying to explore other approaches. One is presented below.

Binary Search based, works if d is not 0

  • Let S = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} - {d} and K = 2 + (\text{number of digits in}\ N)
  • Consider all permutations of elements of S over K places, with repetition allowed.
  • Binary search on an Integer P which satisfies the following conditions.
    • P^{th} permutation is greater than or equal to N
    • (P-1)^{th} permutation is less than N.
  • We can find P^{th} permutation in O(\log_9{P}) time.
  • This approach takes O(\log^2{P_{max}}) time. I even implemented this but sadly it didn’t work for d = 0.

Feel free to share if anyone knows how to make this work for d = 0.

@taran_1407 , any idea?

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

int main() {
// your code goes here
l t;
cin>>t;
for(l i=0;i<t;i++)
{
int n,d;
cin>>n>>d;
//cout<<n<<"\n";
string s=to_string(n);
//cout<<s<<"\n";
string s1=s;
string s2="";
vector v1;
for(l j=0;j<s.length();j++)
{
if(int(s[j])-48==d)
{
v1.push_back(j);
}
}
if(v1.size()==0)
{
cout<<0<<"\n";
continue;
}
l x=-1;
int flag=0;
int flag1=0;
if(s.length()==1)
{
if(int(s[0])-48 ==d)
{
cout<<1<<"\n";
}
else{
cout<<0<<"\n";
}
}
else{
if(d==0)
{
int z=0;
for(l j=0;j<s.length();j++)
{
if(int(s[j])-48==d)
{
z=j;
break;
}
}
for(l j=z;j<s.length();j++)
{
s[j]=‘1’;
}
}
else if(d==9)
{
int v=0;
if(s[0]==‘9’)
{
for(l i=0;i<s.length();i++)
{
s[i]=0;
}
s=‘1’+s;
}
else
{
for(int i=0;i<s.length();i++)
{
if(s[i]==‘9’)
{
v=i;
break;
}
}
while(v>0 &&int(s[v])-48 >=8)
{
v–;
}
if(v==0)
{
if(int(s[v])-48>=8)
{
for(l i=0;i<s.length();i++)
{
s[i]=‘0’;
}
s=to_string(1)+s;
}
else{
s[v]=int(s[v])+1;
for(l i=v+1;i<s.length();i++)
{
s[i]=‘0’;
}
}
}
else{
s[v]=int(s[v])+1;
for(l i=v+1;i<s.length();i++)
{
s[i]=‘0’;
}
}
}
}
else{
for(l j=0;j<s.length();j++)
{
if(int(s[j])-48 == d)
{
x=j;
break;
}
}
s[x]=int(s[x])+1;
for(l j=x+1;j<s.length();j++)
{
s[j]=‘0’;
}
}
//cout<<s<<"\n";
cout<<stoll(s)-stoll(s1)<<"\n";
}

}
return 0;

}

These was my solution but I don’t understand where it was failing can anyone help me??

#include <iostream>
#include <algorithm>
#include <vector>
#include <bitset>
#include <math.h>

using namespace std;


void doer(){
    int n, d,count=0,ith_percent,ith_digit;
    cin>>n>>d;
    bool fnd = true;
    bool fnd2 = false;
    while(fnd){
        fnd2 = false;
        string s = to_string(n);
        int digit_len = s.size();
        for(int i = digit_len;i>0;i--){
                ith_percent = n%(int)pow(10,i);
                ith_digit = ith_percent/pow(10,i-1);
                if(ith_digit==d){
                    fnd2 = true;
                    count+=(int)pow(10,i-1)-n%(int)pow(10,i-1);
                    n+=(int)pow(10,i-1)-n%(int)pow(10,i-1);
                }
            }
            if(fnd2==false){
                fnd=false;
            }
        }
        cout<<count<<endl;
}
int main() {
    // your code goes here
    // freopen("inputf.in", "r", stdin);
    // freopen("outputf.in", "w", stdout);
    int t;
    cin>>t;
    while(t--){
        doer();
    }
    return 0;
}

1 Like

can anyone tell which corner case I missed
#include <bits/stdc++.h>

using namespace std;

#define ll long long int

#define endl “\n”

ll find(ll x,ll num)

{

ll a[x];

ll i=0,sum=0;

while(num!=0 && i<x)

{

    a[i]=num%10;

    num=num/10;

    i++;

}

for(ll j=i-1;j>=0;j--)

{

    sum=sum*10+a[j];

}

return sum;

}

int main()

{

ll tc;

cin>>tc;

while (tc--)

{

    ll n, d;

    cin>>n>>d;

    ll count=0,x=0,k=0,num=0,numx=1,que=n,flag=0;

    while(n!=0)

    {

        count++;

        if(n%10==d)

        {

            flag++;

            x=count;

        }

        n=n/10;

    }

    if(flag==0)

    {

        cout<<"0"<<endl;

    }

    else if(x==1)

    {

        cout<<"1"<<endl;

    }

    else if(d==0)

    {

        for(ll i=0;i<x;i++)

        {

            num=num*10+1;

        }

        k=find(x,que);

        cout<<num-k<<endl;

    }

    else if((count==x && d!=0) || (count-1==x && d!=0) || x==2 && d!=0)

    {

        for(ll i=0;i<x-1;i++)

        {

            numx=numx*10;

        }

        k=find(x-1,que);

        cout<<numx-k<<endl;

    }

    else

    {

        for(ll i=0;i<x;i++)

        {

            numx=numx*10;

        }

        k=find(x,que);

        cout<<numx-k<<endl;

    }

}

return 0;

}

#include
#include <math.h>
using namespace std;

int main() {
int T;
cin >> T;
while(T–)
{
int N, D;
cin >> N;
cin >> D;
int arr[10], i = 0, flag = 0,j;
while(N > 0)
{
arr[i] = N % 10;
i++;
N = N/10;
}
for(j = i-1; j>=0; j–)
{
if(arr[j] == D)
{
flag = 1;
break;
}
}
if(flag == 0)
cout <<“0” <<endl;
else
{
if(j == 0)
{
cout << “1” <<endl;
}
else
{
int res = 10 - arr[0];
int a = 1;
for(int k = 1; k < j; k++)
{
res = res + (9 - arr[k])*pow(10,k);
a = a + pow(10,k);
}
if(D == 0)
{
cout << res+a << endl;
}
else
cout << res << endl;
}
}

}
// your code goes here
return 0;

}

can anyone tell me which corner case i missed??

1
985909924 5
1
895896049 9

Please either format your code or (better!) link to your submission - the forum software has mangled it and it won’t compile! :slight_smile:

https://www.codechef.com/viewsolution/52224707

Thanks!

Consider the test input:

1
959738199 9
1 Like

https://www.codechef.com/viewsolution/52082921
Can someone tell me what corner case I missed?

can anyone tell me what’s wrong with my approach or what test cases i am missing ?

#include <iostream>
#include<cmath>
using namespace std;
unsigned long long int rem(unsigned long long int n,int d){
    unsigned long long int k=0;
    unsigned long long int a=0;
    int m;
    int l=-1;
    m=log10(n);
    m+=1;
    int h=0;
    int flag=0;
    a=n;
    for(int i=0;i<m;i++){
        h=n%10;
        if(h==d){
            l=i;
        }
        n=n/10;
    }
    n=a;
    if( l==-1){
        return 0;
    }
    else{
        for(int i=0;i<m ;i++){
            h=n%10;
            if(h==d){
                if(i<l){
                    for(int f=0;f<10;f++){
                        if(h+f>=10 && ((h+f)%10)!=d){
                            k+=f*pow(10,i);
                            n+=f;
                            flag=1;
                            break;
                            
                        }
                    }
                    if(flag==0){
                        k+=1*pow(10,i);
                        n+=1;
                    }
                    else{
                        flag=0;
                    }
                }
                else if( i>=l){
                    k+=1*pow(10,i);
                    n+=1;
                }
            }
            else{
                if(i<l){
                    a=n/10;
                    a=a%10;
                    
                    if(a+1!=d){
                        for(int f=1;f<10;f++){
                            if(h+f>=10 && ((h+f)%10)!=d){
                                k+=f*pow(10,i);
                                n+=f;
                                break;
                            }
                        }
                    }
                    
                }
            }
            n=n/10;
            if(n==0){
                break;
            }
        }
    }
    return k;
}

int main() {
	unsigned long long int t;
	cin>>t;
	for(unsigned long long int i=0;i<t;i++){
	    unsigned long long int n;
	    int d;
	    cin>>n;
	    cin>>d;
	    
	    d=rem(n,d);
	    cout<<d<<endl;
	    
	}
	
	return 0;
}
1
801523893 9
1
536942010 5

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define mod 1000000007

void testCase(){
ll n, k;
cin>>n>>k;
if(n==k){
cout<<1<<endl;
return;
}
string num = to_string(n);
string sum = “”;
ll carry = 0;
char find = (k+‘0’);

int index = num.size()-1;



if(k==0){
    while(index>=0){
        if(num[index] == find){
        int si = (num.size() - 1 - sum.size());
        int ei = index;
        
        while(ei<=si){
        if(num[si] == find){
            num[si] = (((num[si] - '0') + 1) + '0');
            char newChar = '1';
            sum = newChar + sum;
        }else{
            char newChar = '0';
            sum = newChar + sum; 
        }
        si--;
        }

        }
        index--;
    }
    
    if(sum.size() == 0){
    cout<<0<<endl;
    return;
    }

    cout<<sum<<endl;
    return;
}

while(index>=0){
    if(carry>0){
    ll newNum = (num[index] - '0') + carry;
    carry = newNum/10;
    num[index] = ((newNum%10) + '0');
    }

    if(num[index] == find){
        int si = (num.size() - 1 - sum.size());
        int ei = index;
        while(ei<=si && (si<=(num.size()-1))){
            if(ei == si){
            if(carry==0 && (num[si]==find)){
            char one = '1';
            sum = one + sum;
            ll newNum = ((num[si] - '0') + 1);
            carry = newNum/10;
            num[si] = ((newNum%10) + '0');
            }else{
            ll newNum = ((num[si] - '0') + carry);
            carry = newNum/10;
            num[si] = ((newNum%10) + '0');
            }
            si--;
            continue;
            }

            ll qty = 10 - ((num[si] - '0') + carry);
            if(qty==10){
                qty = 0;
            }
            ll newNum = ((num[si] - '0') + qty + carry);
            carry = newNum/10;
            num[si] = ((newNum%10) + '0');
            char newChar = qty + '0';
            sum = newChar + sum;
            si--;
        }
    }
    index--;
}

if(sum.size() == 0){
    cout<<0<<endl;
    return;
}

int j = 0;
while((j<sum.size()) && (sum[j]=='0')){
    j++;
}
if(j>0){
sum.erase(0, j);
}

cout<<sum<<endl;

}

int main(){
ll t = 1;
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin>>t;
while(t–){
testCase();
}
}

my code is not getting AC. Could anyone tell me which test case is failing my code?

Please either format your code or (better!) link to your submission - the forum software has mangled it and it won’t compile! :slight_smile:

Thanks!!

1 Like

I did it in a different way not the most efficient though.
https://www.codechef.com/viewsolution/52123069

CodeChef: Practical coding for everyone… Please help