Sum of all substrings of a number

Time: O(n)

Space: O(1)

Intuition

Sum of all substrings of a number string. Each digit d at position i (0-indexed from right) contributes d * i * (n-i) to total.

Algorithm

1For digit at position i (1-indexed): it appears in (n-i)*i substrings... compute contribution mathematically.

Common Pitfalls

•Each digit d[i] contributes d[i] * (i+1) * (n-i) * 10^0_weighted. Use contribution formula to avoid O(n^2).

Sum of all substrings of a number.java

Java

// Approach: DP. contribution[i] = d[i] * (i+1) * (n-i). Each digit contributes based on its position.
// Time: O(n) Space: O(1)
class Solution {
    public static int sumSubstrings(String s) {
        int n = s.length();

        int sum = 0;
        int prev = 0;

        for (int i = 0; i < n; i++) {
            int x = s.charAt(i) - '0';
            prev = prev * 10 + x * (i + 1);
            sum += prev;
        }

        return sum;
    }
}

Was this solution helpful?