You are not logged in. Please login at www.codechef.com to post your questions!

×

# YVNUM Editorial

Author and Editorialist: Hussain Kara Fallah
Tester: Michael Nematollahi

NONE

# PROBLEM:

Given a decimal integer $N$ (with no zeroes at all even as intermediate digits). Consider all left cyclic shifts of $N$. The left cyclic shift is the operation of removing the leftmost digit from the number and appending it to the end.

Suppose $N = 123$ then all left cyclic shifts are {123,231,312}. So you start with $N$ and repeat the mentioned operation $N-1$ times.

Yalalovichik number of $N$ is equal to the concatenation of all these cyclic shifts.

For the previous example:

$Y = 123231312$.

Given $N$, you need to compute the value of $Y$ modulo $10^9+7$

Length of $N$ may reach $10^5$

# EXPLANATION:

Let's assume that length of $N$ is equal to $L$. We know that:

$N = a_0*10^{L-1} + a_1*10^{L-2} + a_2*10^{L-3} + ... + a_{L-1}$

Assuming that digits are indexed from $0$ to $L-1$ and from left to right. $a_0$ represents the leftmost digit. So let's assume we need to do one shift operation, how to erase the leftmost digit?

$N' = N - a_0*10^{L-1}$

$N'$ is equal to the value of $N$ after removing the leftmost digit.

Let's assume that the number resulting from the shift is $M$ so:

$M = N' * 10 + a_0$

so now the number resulting from the shift is $M$ we need to append it to our final answer. At the beginning the answer $ans = N$. To append it let's shift $ans$ to the left by $L$ digits and simply add $M$.

$ans = ans * 10^L + M$

This is for the first shifting operation, to solve the problem repeat this operation $N-1$ times, but don't forget to continue working on the shifted number.

We only need to calculate $10^L$ and $10^{L-1}$, this can be done in linear time or faster if you prefer.

To maintain the answer modulo $10^9+7$ we calculate the powers mentioned above modulo $10^9+7$ and we always take our results modulo $10^9+7$ after each subtraction or multiplication or addition.

Refer to the implementations for more details.

Total Complexity $O(L)$

# AUTHOR'S AND TESTER'S SOLUTIONS:

TESTER's solution

This question is marked "community wiki".

asked 23 Dec '18, 23:10

1081032
accept rate: 0%

19.8k350498541

It could be rewritten $M = N * 10 - a_0 * (10^L - 1)$. So we only need to calculate $10^L$.

And we can do it while calculating $N$.

(26 Dec '18, 01:06) 3★

 0 Thanks, very simple and good editorial. answered 25 Dec '18, 20:55 4★me17b016 41●2 accept rate: 0%
 0 answered 26 Dec '18, 09:00 3★eugalt 282●7 accept rate: 4%
 0 Why did you do cur+=MOD ? answered 26 Dec '18, 12:44 1 accept rate: 0%
 0 Thanks, for this easy explanation . i am constantly getting TLE for this but now i can solve this answered 26 Dec '18, 19:56 1●1 accept rate: 0%
 0 i just want to know that is the constraint that N<=10^5 for integer or string of length 10^5 answered 26 Dec '18, 20:30 1 accept rate: 0%
 0 The link to my solution: https://github.com/executable16/CodeChef/blob/master/Yalalovivhik.cpp answered 29 Dec '18, 03:52 1●1 accept rate: 0%
 0 Can anybody help? Simple solution but doesn't work: https://ideone.com/nEqSN1 answered 04 Jan, 17:45 2★shardic 2●2 accept rate: 0%
 0 I was getting TLE as i was doing in O(L*L),now i can do it,good editorial. answered 20 Jan, 10:58 0 accept rate: 0%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,684
×74
×51

question asked: 23 Dec '18, 23:10

question was seen: 2,298 times

last updated: 20 Jan, 10:58