Product of sum of all subarrays of an array
I've been able to find sum of all subarrays, product of all subarrays, product of the sum of all subarrays in O(n) but I'm not able to find a pattern for this.
Explanation:
array = {1,2,3}
ans = (1)*(2)*(3)*(1+2)*(2+3)*(1+2+3) = 540
There can be 10e5 elements in the array.
Can someone please help me find a way to solve this in linear time?
Thank you!
Explanation:
array = {1,2,3}
ans = (1)*(2)*(3)*(1+2)*(2+3)*(1+2+3) = 540
There can be 10e5 elements in the array.
Can someone please help me find a way to solve this in linear time?
Thank you!
Why do you only have (1+2) and (2+3).
What about (1+3) ?
At any rate, the value as you've described it could be millions of decimal digits long.
Does that sound reasonable to you?
If you have a link to the problem, post it.
What about (1+3) ?
At any rate, the value as you've described it could be millions of decimal digits long.
Does that sound reasonable to you?
If you have a link to the problem, post it.
Last edited on
1+3 can't be included as its not a subarray, we're talking about contiguous subarrays like [1], [2], [3], [1,2], [2,3], [1,2,3].
Yeah, I know the final value can be infinitely large, we can later apply modulus to improve that.
Actually I myself was working on such stuff so there doesn't exist a specific problem.
Yeah, I know the final value can be infinitely large, we can later apply modulus to improve that.
Actually I myself was working on such stuff so there doesn't exist a specific problem.
| Actually I myself was working on such stuff so there doesn't exist a specific problem. |
okay
You say you already know "product of the sum of all subarrays".
Isn't that exactly what you're doing?
Last edited on
I don't why you're so confused with the question. Simply the question goes as follows that we need to calculate product of sum of all subarrays (example given in previous replies and the post itself.) I've already wasted around a week trying to figure out a way to get this in linear time but I didn't succeed. That's why I'm asking someone to help me I'm getting nowhere in this question.
Constraints:
array size: 1 < size < 10e5
elements: 0 <= element <= 10e9
Time complexity: <= O(nlogn)
Constraints:
array size: 1 < size < 10e5
elements: 0 <= element <= 10e9
Time complexity: <= O(nlogn)
| oyehoye696906 wrote: |
|---|
| I don't why you're so confused with the question. |
Your elements can be of size 109. There could be up to 105 of them. And you seriously think you are going to represent their product in an integer variable?
Or are you going to give your answer modulo something?
State the whole problem. State which particular competition it comes from.
This appears to be some sort of a starting point to find out the real nature of this problem.
https://www.geeksforgeeks.org/sum-of-all-subarrays/
https://algorithms.tutorialhorizon.com/sum-of-all-sub-arrays-in-on-time/
https://www.geeksforgeeks.org/sum-of-all-subarrays/
https://algorithms.tutorialhorizon.com/sum-of-all-sub-arrays-in-on-time/
Last edited on
@lastchance, We'll obviously use modulo like 10e9+7 to get the final answer. I myself thought of this problem and I was searching for the answer.
| I don't why you're so confused with the question. |
You are obviously the one who is totally confused here.
I know exactly what you are looking for.
You are looking for the "product of the sum of all subarrays".
That's what you are looking for, whether you know it or not.
(I can't fathom why you don't know that! Jesus!)
Anyway, you also state in your original braindead question that you already know the "product of the sum of all subarrays".
Now can your tiny brain understand the problem?
There are N(N+1)/2 subarrays so you have that many factors. Clearly multiplying them is O(N2) so to do this faster, you need some way to reduce the factors. I've been playing around with this a little and I can't figure anything out.
What makes you think this can be done in O(N) time?
What makes you think this can be done in O(N) time?
Topic archived. No new replies allowed.