Problem: [Problem Link][1]
Prerequisites: Basics of Modular Arithmetic
We will solve the problem by breaking into three parts:
Let MOD = 109+7
Part 1: Finding the MOD of large number
Let the given number be A, where |A| denotes the number of digits in A. Let Ai represents the ith digit and l = |A| then
A%MOD = Σ Ai×10l-i % MOD
= Σ (Ai×(10l-i % MOD))%MOD
For example
12345%MOD = (1×104)%MOD + (2×103)%MOD + (3×102)%MOD +(4×101)%MOD + (5×100)%MOD
One important point here is 10i is used many times, hence we can calculate and store them.
Here is my code example:
vector<int> arr(100005);
vector<ll> dig = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; // for converting char to digits
arr[0] = 1;
for(int i=1, i < 100005; i++)
arr[i] = ((arr[i-1]×10)%MOD);
// let s contains the number in string format ( since number is very large) and l contains the length
int mi = 0;
for(int i = s.size()-1; i>=0; i--){
mi += ((dig[s[i]-'0']×arr[l-i-1])%MOD);
}
mi = mi%MOD;
Part 2: Generating next shift from previous
For generating the next shift from previous shift
Anext = Aprev ×10 - 10l × Aprev1 + Aprev1
For Example :
23451 = 12345*10 - 105×1+1
= 123450 - 100000 + 1
Yeah, sure you should perform subtraction first and then multiplication to prevent overflow, but I used long long.
Here is my Code example
int l = s.size();
// for having the ith shift where mi contains the i-1th shift
mi = (((mi×10)%MOD + dig[s[i]-'0'])%MOD - (dig[s[i]-'0']×arr[l])%MOD)%MOD;
Part 3: Combining the result
If you are with me till now, this part is the most simplest among the all. The idea is how you can generate the number using the digit. For example
12345 = (1×104) + (2×103) + (3×102) +(4×101) + (5×100)
= ((((( 1 ) × 10 + 2 ) × 10 + 3 ) × 10 + 4 ) × 10 + 5 )
For input 123, we can get the combine result as follows :
total = ((( 123 ) × 103 + 231 ) × 103 + 312 )
Working on the similar lines, you can combine the next shift with the previous result. Let total represent the total score till now, then combining process involves
total = ((total×arr[l])%MOD + mi)%MOD;
Time complexity: ◯(n), where n = |N|
Code: [Solution Link][2]
[1]: CodeChef: Practical coding for everyone
[2]: CodeChef: Practical coding for everyone