How to find the product of all the possible subarrays in an array in linear time?

Question

Suppose I have an array A[4] = {5,6,2,4}

The sub-arrays are: {{5}, {6}, {2}, {4}, {5, 6}, {6, 2}, {2, 4}, {5, 6, 2}, {6, 2, 4}, {5, 6, 2, 4}}

I need the array containing product of each sub-array as output i.e. {5, 6, 2, 4, 30, 12, 8, 60, 48, 240}

This is my O(n^2) approach:

const int a = 4;
const int b = 10; //n(n+1)/2
int arr[a] = {5, 6, 2, 4};
int ans[b] = {0};
int x = 0;
for(int i = 0; i < n; i++) {
  prod = 1;
  for(int j = i; j < n; j++) {
    prod *= arr[j];
    ans[x++] = prod;
  }
}

//ans is the o/p array

I was wondering if this can be found in O(n) complexity or not? Thanks!

Answer 1

No it's impossible, because the size of the result is quadratic (n(n+1)/2 specifically). Just writing every entry of the result already costs quadratic time regardless of how easy it is to compute it.