You are given an integer array A of length 10, initially containing all zeros. You must perform the following sequence of operations: 1. For i from 1 to 10 (inclusive), update A[i] = A[i] + i. 2. For every index i such that i is divisible by 2, update A[i] = A[i] + A[i/2]. 3. For every index i such that i is divisible by 3, update A[i] = A[i] + A[i/3]. 4. Compute the value S = sum(A[i] * i) for i from 1 to 10. What is the final value of S?
Start with A = [0,0,0,0,0,0,0,0,0,0]. After step 1, A[i] = i, so A = [1,2,3,4,5,6,7,8,9,10]. Step 2 updates even indices: A[2]+=A[1]→3, A[4]+=A[2]→4+3=7, A[6]+=A[3]→6+3=9, A[8]+=A[4]→8+7=15, A[10]+=A[5]→10+5=15. Step 3 updates multiples of 3: A[3]+=A[1]→3+1=4, A[6]+=A[2]→9+3=12, A[9]+=A[3]→9+4=13. Final A = [1,3,4,7,5,12,7,15,13,15]. Compute S = Σ(A[i]*i) = 1*1 + 3*2 + 4*3 + 7*4 + 5*5 + 12*6 + 7*7 + 15*8 + 13*9 + 15*10 = 1 + 6 + 12 + 28 + 25 + 72 + 49 + 120 + 117 + 150 = 580.