DIVNINE - Editorial

PROBLEM LINK:

Contest
Practice

Author: Kevin Atienza
Tester: Kevin Atienza and Gedi Zheng
Editorialist: Kevin Atienza

PREREQUISITES:

String processing, divisibility rules

PROBLEM:

Turn a given number N into a multiple of 9 using a sequence of moves. The only allowed moves are to increment or decrement a digit by one, but you cannot increase a digit 9 or decrease a digit 0, and the resulting number must not contain any leading zeroes unless N has a single digit. (This means that a number can only have a leading zero if it is 0)

What is the minimum number of moves needed?

QUICK EXPLANATION:

Let S be the sum of the digits of N, and let M be S \bmod 9. If N has more than one digit and S < 9, then the answer is 9 - M. Otherwise, the answer is \min(M, 9-M).

EXPLANATION:

Before we answer the problem, let’s first discuss which numbers are divisible by 9.

Divisibility by 9

When is a number N divisible by 9? You might remember a really simple way of checking whether a number is divisible by 9:

A number x is divisible by 9 if and only if the sum of the digits of x is divisible by 9.

Let’s show why this is true. Actually, we’ll show the following stronger statement:

The remainder when x is divided by 9 is equal to the remainder when the sum of the digits of x is divided by 9.


Proof:

Suppose the digits of x from most to least significant are x_{d-1}, x_{d-2}, \ldots, x_0, i.e.

x = x_0 + 10x_1 + 100x_2 + 1000x_3 + \cdots + 10^{d-1}x_{d-1}

The sum of digits of x, which we denote as S(x), is therefore

S(x) = x_0 + x_1 + x_2 + x_3 + \cdots + x_{d-1}

Now, x - S(x) is equal to the following:

x - S(x) = 9x_1 + 99x_2 + 999x_3 + \cdots + (10^{d-1} - 1)x_{d-1}

x - S(x) is clearly divisible by 9, but this can only happen if x and S(x) have the same remainder when divided by 9.


Computing the answer

The fact above actually allows us to quickly compute the remainder of N when divided by 9: N \bmod 9 is simply S(N) \bmod 9. But S(N) is easy to compute, and from the upper limit of N, we are sure that S(N) \le 9\cdot 10^5. Therefore, we can easily compute S(N) \bmod 9 with an additional step.

This is great, but how does this help us answer the question? Well, note that the only allowed operations are to increment or decrement a digit, and each operation increases or decreases the sum of digits by exactly one. This gives us a few observations:

  • If there are I increment operations and D decrement operations, then the resulting sum of digits is S(N) + I - D, and we want this to be divisible by 9.
  • An optimal sequence of operations contains only increment operations or only decrement operations. This is because each pair of increment and decrement operation cancels each other out in terms of the sum of digits.
  • If a sequence of operations consists purely of increment operations (i.e. D = 0), then I = (9 - S(N)) \bmod 9. (Note that this is always nonnegative)
  • If a sequence of operations consists purely of increment operations (i.e. I = 0), then D = S(N) \bmod 9.

Thus, our current answer is \min((9 - S(N)) \bmod 9, S(N) \bmod 9). But is this correct? Consider the following case:

N = 100000000012

We have S(N) = 4, so our “answer” is \min((9 - 4) \bmod 9, 4 \bmod 9) = \min(5, 4) = 4. However, we cannot decrement this number four times, because we are not allowed to introduce leading zeroes! How do we fix this?

Well, we can fix this by noting that we can only introduce leading zeroes by decrementing digits, and that we are only forced to introduce leading zeroes if the sum of the digits itself is less than 9. Therefore, our “adjusted” solution is the following:

\text{Answer} = \begin{cases} \min((9 - S(N)) \bmod 9, S(N) \bmod 9) & \text{if $S(N) \ge 9$} \\ (9 - S(N)) \bmod 9 & \text{otherwise} \end{cases}

This solution now successfully gives the correct answer 5 for the N above.

But there is still a problem! Consider the case N = 1. The formula above gives the answer 8, but in fact we can decrement N to become 0 this time, because N has a single digit! Therefore, we need to adjust the above answer again:is the following:

\text{Answer} = \begin{cases} \min((9 - S(N)) \bmod 9, S(N) \bmod 9) & \text{if $S(N) \ge 9$ or $N$ has a single digit} \\ (9 - S(N)) \bmod 9 & \text{otherwise} \end{cases}

Now that’s better!

What about incrementing? Will there ever be a case where we are required to increment so many digits that we run out of places to increment? The answer is no, because we only get stuck if the number consists purely of 9 digits, i.e. 99999999\ldots 999, but this number is divisible by 9, so we are guaranteed not to exceed this number!

Time Complexity:

O(D) = O(\log N), where D is the number of digits of N

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter
Tester 1
Tester 2

6 Likes

#include<stdio.h>

int main()
{
int t;
int len=0;

scanf("%d",&t);
while(t--)
{  char ch;
long long a;
    char c = 0;

while(c<33)
//c = fgetc_unlocked(stdin);
c = getc(stdin);
a = 0;
while(c>33)
{
a = a + c - ‘0’;
len++;
//c = fgetc_unlocked(stdin);
c = getc(stdin);
}
//printf("%d\n",a);
if(a%9==0)
{

printf("0\n");
continue;

}

int q=a/9;
int add= (q+1)9-a;
int remove=a-q
9;
if(len>1&&a<=remove)
remove=9;

printf("%d\n",add>=remove?remove:add);

}

}
whats the problem in this solution…

I think you did a very small mistake of mis understanding questions. See your output is wrong for single digit numbers . If input is given as 1 your output is 8 but it should be 1 because you can convert 1 to zero as it is a single digit number. And single digit numbers were allowed to be made 0

What should be the solution for say 79?
Shouldn’t it be 7?

You cannot increment 9 and so you can decrement 79 to reach 72 or you can decrement 9, 8 times and increase 7 by 1 to reach 81 again 7 operations in total.

With the above solution the answer will be 2

#include<stdio.h>
int main()
{
int n,sum,i,count=0;
long int t=0;
scanf("%ld\n",&t);
int a[t];
for(i=1;i<=t;i++)
{
sum=0;
while((n=getchar())!=’\n’)
{
n-=‘0’;
sum+=n;
count++;
}
if(count>1 && sum<9)
{
a[i-1]=9-(sum%9);
}
else
{
if(sum%9<=(9-sum%9))
a[i-1] = sum%9;
else
a[i-1] = 9-sum%9;
}
}
for(i=0;i<t;i++)
printf("%d\n",a[i]);
return 0;
}
What is the problem with this?

import java.util.*;
public class Divisible
{
public static void main(String []args)
{
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
for(int i=0;i<n;i++)
{
String s=sc.next();
char a[]=s.toCharArray();
int ans=0;
for(char c:a)
{
int d=c;
d=d-48;
ans+=d;
}
ans=ans%9;
if(ans>4)
{
System.out.println(9-ans);
}
else
{
System.out.println(ans);
}
}
}
}

You can increment 7 by 2 to get 99…

Can anyone tell why my solution gives WA ? Tried lots of cases, still can’t find any test case where it fails.

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

int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);		cout.tie(0);

int test;
cin>>test;
while(test--){
string s;	
//scan number in a string as (10^(10^5)) can be stored even in long long int
cin>>s;
int i,j,k=0,dec=0,inc=0;// we have to find (sum of digits)%9
for(auto ch:s){
	k+=ch-'0';
	dec+=(dec<19?(ch-'0'):0);
	inc+=(inc<19?('9'-ch):0);
	k%=9;
}
//dec tell maximum place till which number can be decreased, similar is inc
// k is storing the amount of increment to make it a multiple of 9

dec-=1;//first digit can't be 0
k=9-k;
//if incresing is allowed and (cost of inc < cost of dec  or dec is not allowed)
if(inc>=k && (k<9-k || dec<9-k))
	cout<<k<<"\n";
else cout<<9-k<<"\n";
// cout<<"inc : dec : "<<inc<<" "<<dec<<"\n";


}
	return 0;
}

#include
#define lld long long
#define mod 1000000007
using namespace std;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

lld n,t;
cin>>t;
while(t–)
{
cin>>n;
if(n % 9){
if(n % 9 >= 5) cout<<9 - (n%9)<<endl;
else cout<<n%9<<endl;
}
else
cout<<“0”<<endl;
}
return 0;
}

Can anyone please tell me which part is wrong in my code. I tried many test cases and couldn’t find any wrong answer but still, submission shows WA.

#include <iostream>
using namespace std;

#define ll long long int
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        ll n;
        cin>>n;
        ll rem, sum=0, num=n, first_digit;
        while(n)
        {
            rem=n%10;
            sum+=rem;
            first_digit=n;      ///to store the first digit of the number
            n=n/10;
        }
        if(sum<9 && num>9)      ///if sum is less than 9 but the number is greater than 9
        cout<<9-sum<<endl;
        else{
            rem=sum%9;
///check if without first digit the number is divisible by 9 then make the fist digit 9 as well
            if((sum-first_digit)%9==0 && num>9)   
///since we can't decrement the first digit to zero so we increase it to 9.  
                cout<<9-first_digit<<endl;         
            else
                cout<<min(9-rem,rem)<<endl;
        }
    }
    return 0;
}

The constraint for the number N is 10^(10^5) and such a huge number can not be stored in long long. Happy codding.

What’s wrong with my solution?

#include<bits/stdc++.h>
using namespace std;
#define     ll              long long
#define     MAX             100000
#define     FI              freopen("input.txt","r",stdin)
#define     FO              freopen("output.txt","w",stdout)
#define     fast            ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define     sc(a)           scanf("%d",&a)
#define     sc2(a,b)        scanf("%d %d",&a,&b)


int main()
{
    ll t;
    cin>>t;
    while(t--)
    {
        string s;
        cin>>s;
        ll sum=0;
        for(auto x:s)
        {
            sum+=x-'0';
        }
        ll a,b;
        a = sum%9;
        b = 9-a;
        cout<<min(a,b)<<"\n";
    }
    return 0;
}

In case of 79 your code giving answer as 2 but correct answer is 7…
for explanation look upper discussion part.

using same approach with string gives AC, but with boost library and cpp_int gives TLE. can someone please explain. thanks in advance.
use of boost library gives TLE : CodeChef: Practical coding for everyone
using string gives AC : CodeChef: Practical coding for everyone

#include <stdio.h>

int main(void)
{
long long int num,i,t,remndr,sec=0,p,extra,flag[2];
scanf("%lld",&t);
for(i=0;i<t;i++)
{
scanf("%lld",&num);
extra=num%9;
if(num<10)
{
goto label1;
sec=num>9-num?9-num:num;
}
if(extra==0)
{
sec=0;
goto label1;
}
else
{
p=num;
flag[0]=0;
while(num>0)
{
remndr=num%10;
num=num/10;
if(remndr-extra)
{
flag[0]=1;
break;
}
}

     if(flag[0]==1)
     {
         flag[1]=0;
         extra=9-extra;
         num=p;
         while(num>0)
            {
              remndr=num%10;
              num=num/10;
              if(remndr+extra<10)
                   {
                     flag[1]=1;
                     break;
                   }
            }  
     }        
 }
 if(flag[0]==0)
  {
    sec=9-extra;  
  }
 else if(flag[0]==1&&flag[1]==0)
  {
      sec=9-extra;
  }
  else
  { 
    sec=extra>9-extra?9-extra:extra;
  }
  label1:
  printf("%d\n",sec);
}

return 0;
}
this code is giving a proper output except for integers more than 19 digits the output is constant that is always yhe answer is 2 please suggest the solution