PALL9 - Editorial

Problem LInk : https://www.codechef.com/CCOD2020/problems/PALL9

A number is divisible by 9, if the sum of the digit is divisible by 9.

Image for reference:

For N belongs to odd except 1,

There always exist a unique x for which the sum is divisible by 9 i.e.
( 2*(a + b) + x ) % 9 = 0
For every a, b , there exist a unique x

Example :
for N = 5 ,a = 4 ,b = 9
a + b + x + b + a => 26 + x must be div by 9
Then x must be 1.

So the number of pallindromes, if the length is odd is pow(9, len/2 ).

Similarly for N = even
Let N = 6
For every a, b , there always exist a unique x to make sum div by 9 i.e.
( 2*(a + b + x)) % 9 = 0 // as in the case of odd

Example
For N = 6
a = 4
b = 9
a + b + x + x + b + a = 26 + 2x must be div by 9
Then x must be 5

So the number of pallindrome, if length is even ,is pow( 9, (len/2) – 1)

Now, the question left to calculate the sum of Numbers :

NOTE : THIS METHOD IS NOT VALID FOR N = 1 OR N = 2

Consider the Kth position in N.

At Kth position , each digit [0,9] will repeat {Total ways of forming favoulable pallindromes} / 9 times.

So, the sum of all the digits on Kth position = 45*{ways/9}

So the sum can be easily found, For ref see code.

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD 1000000007

ll power(ll a, ll b)
{
    if (b == 0)
    {
        return 1;
    }
    ll temp = power(a, b / 2);
    temp = (temp * temp) % MOD;
    if (b % 2 != 0)
    {
        temp = (temp * a) % MOD;
    }
    return temp;
}

int main()
{   
    ll test;
    cin >> test;

    while(test--){
        ll len;
        cin >> len;
        // this method will not work for n = 1 and 2, so
        if(len == 1){
            cout << "9" << endl;
            continue;
        }
        if(len == 2){
            cout << "99" << endl;
            continue;
        }
        ll ways = len / 2;
        if (len % 2 == 0)
            ways--;
        ll res = power(9, ways-1);
        ll sum = 0;
        for (int i = 0; i < len; i++)
        {
            sum = sum * 10 + (45 * res                                                                                                                                  );
            sum = sum % MOD;
        }
        cout << sum << endl;
    }
    return 0;
}
3 Likes

I believe this question is copied from an infosys.hackerearth.com question from 2 weeks ago.

3 Likes

This question was asked by my friend. I googled but not able to find the source then. I assume this contest(that you are mentioning) was running on that time that’s why I was not able to find . I put it down in contest as I was fascinated by the beauty of the question and want to share my approach.

Btw, Thanks…I will be more careful from next time. :blush: :blush:

3 Likes

can somebody please explain how this result comes?
So the number of pallindromes, if the length is odd is pow(9, len/2 ).

The contest is rated?XD

if length is odd then,
let n = 5,
then for making it pallindrome , first 2 digits and last two digits must be same.
So the only left digit is middle one,
And there is always one way to fill the middle digit to make sum divisible by 9

Thanks :grinning:

here x is unique for any values of a and b (taking size as 5 or 6) so. so how can u say x appears only
power(9,ways-1) times.
AS in sol. u take x occurence always as res.
what is the proof?
@piyushbhutani @nitika_789

Please print the sequences and test it.
Make a brute force code and observe it,

means the proof is only observation (for which also i have to write brute force ). :pensive: :pensive:

NO buddy!! The only proof is not brute force. It is the mathematics. Make digits as
“abxba” and try to find range of x for ranges of a and b.
I hope u get it.

so i m also asking the same how to find range for x for any values of a and b??

this is for N = 5
Min value of a, b = 1

Max value of a, b = 9;

so min sum = a + b = 2

max sum = a + b = 18

as the number is pallindrome so

K = 2*(a + b) + x

values of 2(a +b) can be 4, 6, 8 …36

to make K div by 9 , values of corresponding x:

4 -> 9

6 -> 3

8 -> 1

10 -> 8

36 -> 9 (cant be 0, as in quesiton it is given that deciaml representaion doesnot contain zero)

Now , I hope u get the mathematics behind it.

2 Likes

thank u so much bruhh :grinning:

Welcome bro. I am glad , you get it.

Well, this is a very beautiful problem. After seeing the contraint N=10^5, I first wrote a digit dp solution with O(T+N*10*10). Then after seeing editorial I realised that It can be solved much easily and much lesser complexity O(T*log(N)) for N=10^18 also by using simple math by just optimizing the “sum” process too in log(N) instead of looping through N.
you can calcultate sum as this way

sum = (power(10, len)-1) * power(9, ways-1) * 5;

for 4 it should be 5 right? bro :thinking:

See I dont understand one part of solution. I was also initially doing as in editorial. Suppose we have a 5 digit number. So it can be A B X B A where X is determined by values of blanks. Now I know contribution of 10^4 will always be 45*(choices for B) = 45*9. Similarly for B. So what remains is contribution of centre element, that is 10^2 here. Now I dont understand how each element, say X=1, 2, ... 9 will also have same contribution as 45*9

According to editorial we are assuming that all values for X are occurring same number of times, that is equal to 45*9 in this case.

A simple proof or explanation of this will be great, I hope my question is clear!

PS: 45*9 is same as 45*res in code

why again ways-1?

At Kth position , each digit [0,9] will repeat {Total ways of forming favoulable pallindromes} / 9 times.

So, the sum of all the digits on Kth position = 45*{ways/9}
can anyone elaborate it more with example?? how this formula came up