DIVNINE - Editorial

editorial
,
1

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

5 Likes
2

#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-q9;
if(len>1&&a<=remove)
remove=9;

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

}

}
whats the problem in this solution…

3

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

4

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

5

You can increment 7 by 2 to get 99…

6

#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?

7

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);
}
}
}
}