Sam and substrings Discussions | Algorithms | HackerRank
We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
intsubstrings(stringn){constintMOD=1e9+7;longlongresult=0;// Convert character to integer value with "- '0'"// dp[i] represents sum of all substrings ending at index ilonglongdp=n[0]-'0';result+=dp;// Add substrings sum ending at index 0for(inti=1;i<n.length();i++){// Sums all substrings ending at index i, // sums all substrings ending at index i-1,// sums all substrings ending with current digit (n[i]).dp=(dp*10+(i+1)*(n[i]-'0'))%MOD;result=(result+dp)%MOD;}return(int)result;}
Here's how it works:
We initialize a variable result to 0, which will store the final sum of all substrings.
We also initialize a variable dp to the value of the first digit of the string, since the sum of all substrings ending at index 0 is simply that digit.
Then we iterate over the rest of the string, and for each index i, we compute the sum of all substrings that end with the digit at index i.
The sum of all substrings ending at index i is simply the sum of all substrings ending at
index i-1, plus the sum of all substrings that end with the current digit (which can be obtained by adding the digit to the end of all substrings that end at index i-1).
We update result by adding the sum of all substrings ending at index i to it.
Finally, we return the result modulo 10^9+7, as requested.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Sam and substrings
You are viewing a single comment's thread. Return to all comments →
Here is a C++ solution
Here's how it works:
We initialize a variable result to 0, which will store the final sum of all substrings.
We also initialize a variable dp to the value of the first digit of the string, since the sum of all substrings ending at index 0 is simply that digit.
Then we iterate over the rest of the string, and for each index i, we compute the sum of all substrings that end with the digit at index i.
The sum of all substrings ending at index i is simply the sum of all substrings ending at index i-1, plus the sum of all substrings that end with the current digit (which can be obtained by adding the digit to the end of all substrings that end at index i-1).
We update result by adding the sum of all substrings ending at index i to it. Finally, we return the result modulo 10^9+7, as requested.