Subarray Digit Sums
Given an array of N positive integers, compute the sum of digit sums for all possible contiguous subarrays. A contiguous subarray is defined by a starting index i and an ending index j (inclusive, 0 <= i <= j < N). For each subarray, calculate the sum of its elements' digits. Then, sum up these digit sums for all possible subarrays.
Input
The first line contains an integer N (1 <= N <= 200000). The second line contains N space-separated positive integers a_1, a_2, ..., a_N (1 <= a_i <= 10^9).
Output
Print a single integer, the total sum of digit sums of all contiguous subarrays.
Constraints
1 <= N <= 200000 1 <= a_i <= 10^9
Example 1
3 1 2 3
20
Subarrays: [1] (ds=1), [2] (ds=2), [3] (ds=3), [1,2] (ds=1+2=3), [2,3] (ds=2+3=5), [1,2,3] (ds=1+2+3=6). Total = 1+2+3+3+5+6 = 20.
Example 2
2 10 20
6
Subarrays: [10] (ds=1), [20] (ds=2), [10,20] (ds=1+2=3). Total = 1+2+3 = 6.
Hints
Similar problems
- Count Distinct Prefix SumsMedium
- Count Pairs with Equal Digit GCDMedium
- Distinct Elements in PrefixMedium
- Count Pairs with Equal Digit SumMedium
- Maximum Average SubsegmentMedium
- Array Prefix Maxima and MinimaMedium
More topics: Arrays problems, Prefix Sums problems, Math and Number Theory problems
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
3 1 2 3
2 10 20