CODEWITHSUNDEEP
c++algorithmdivide-and-conquer
Ashkan Khademian
Ashkan Khademian

Reputation: 357

Sum of product of all subarray of length less than equal to k

I'm trying to solve the following problem.

Given array of integers with size n called A. Find the sum of product of all possible subarrays from A with the length less than k with modulo M. e.g.

A = [9 1 90]
k = 2
M = 10

then the asked sum will be:

sum = (9 + 1 + 90 + (9 * 1) + (1 * 90)) % 10 = 9

I first tried a simple dynamic programming as long as an iteration over the A and it took O(nk) and it got time limit error. The mentioned code in cpp is as follows:

int main() {
    int n, k, M;
    cin >> n >> k >> M;
    long long int D[n][n];
    int sum_ = 0;
    for (size_t i = 0; i < n; i++)
    {
        int temp;
        cin >> temp;
        temp %= M;
        D[i][i] = temp;
        sum_ = ((sum_ + temp) % M);
    }

    for (size_t t = 1; t < k; t++)
    {
        size_t i = 0, j = t;
        while (j < n) {
            int mid = (i + j) / 2;
            int temp = (D[i][mid] * D[mid+1][j]) % M;
            D[i][j] = temp;
            sum_ = ((sum_ + (temp % M)) % M);
            i ++;
            j ++;
        }
        
    }
    cout << sum_ << endl;
    return 0;
}

So now I'm thinking of maybe a Divide and Conquer method to solve it in O(nlogn) but I can not come up with any good solution.

Is there any way to solve this problem in a better time complexity of O(nk) (or O(n.n)).

Upvotes: 0

Views: 620

Answers (1)

reza
reza

Reputation: 15

We can write a solution with O(n) complexity using dynamic programming.

First we define dp[i] as sum of product of all subarrays of length less than or equal to k starting at ith position in array A. We also define b[i] as the product of the subarray of length k starting from the ith position in array A (if i<=n-k) and as the product of the subarray starting from ith position and ending at the nth position (if i>=n-k).

We can easily determine that b[i] = ((b[i+1] * a[i]) / (a[i+k])) % M if(i+k<=n) and b[i] = (b[i+1] * a[i]) % M if(i+k>n).

We can also determine that dp[i] = (a[i] * (dp[i+1]-b[i+1]) + a[i]) % M if(i+k<=n) and dp[i]= (a[i] * dp[i+1] + a[i]) % M if (i+k>n)

The answer to the question would be the sum of dp[i] for 1<=i<=n

Thus the complexity would be O(n).

Upvotes: 1

Related Questions