Sam and substrings Discussions | Algorithms | HackerRank
  • + 1 comment

    Here is a C++ solution

    int substrings(string n) {
        const int MOD = 1e9 + 7;
        long long result = 0;
        // Convert character to integer value with "- '0'"
        // dp[i] represents sum of all substrings ending at index i
        long long dp = n[0] - '0'; 
        result += dp; // Add substrings sum ending at index 0
        
        for (int i = 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.