E- Σ[k=0..10^100]floor(X／10^k) AtCoder Beginner Contest 233
Approach-
As we see the pattern, each time the number gets divided by 10 and then summed up to give the final answer.
Observation-1
As we notice that for a number if it has n digits then the most significant digit contributes n times to the final sum, the second most significant contributes n-1 time and so on.
Observation-2
This final sum can be represented as sum of the prefix sums of the digits of the number. For example 1225 has to be written as 1, 3, 5, 10 as prefix sum array.
Now we just have to add these numbers starting from the backside of the array using the carry ahead method of addition. The sum is 1360 for the above example. All the operations should be done by taking the number as string input since the constraints are very high.
Below is the code matching with the exact explanation above.
Code-
string s;
cin>>s;
long long n=s.length(), prefixsum[n];
prefixsum[0]=s[0]-'0';
for(long long i=1;i<n;i++)
{
prefixsum[i]=prefixsum[i-1]+(s[i]-'0');
}
long long c=0;
string ans="";
for(long long i=n-1;i>=0;i--)
{
if(prefixsum[i]+c>9)
{
ans+=to_string((prefixsum[i]+c)%10);
c=(prefixsum[i]+c)/10;
}
else
{
ans+=to_string(prefixsum[i]+c);
c=0;
}
}
if(c>0)
ans+=to_string(c);
reverse(ans.begin(), ans.end());
cout<<ans;
Other Problems from this Contest-
Disclaimer- Everything is published after the actual contest gets over.