Intuition
We need all possible subarrays of this array, add them all to a list, then extract elements on the basis of a range from this list, add them up and return - pretty straightforward.
This code generates all possible subarrays in an array of length n. Remember, subarrays are different from subsets which are different from subsequences.
In the below code we are computing the running sum in the range left..right
- but we are also MOD-ing it with .
Well because since the answers could be very huge, the question author asked us to do this.
Here’s how it works:
Usually this is done just so the author can verify our answers with theirs without actually dealing with large numbers since that’s computationally heavy. Is there a change that our actual answer is incorrect but MOD-ing it turns it into a correct answer? Well, yes. But according to theory of cryptography and the Pigeonhole Principle - that’s rare (but possible, it’s called a hash collision). Since we are not just verifying a single test case but hundreds of them - it’s near impossible for all test cases to just ‘coincidentally’ pass. Hence, this works.
Code
Python3
Big O Analysis
-
Runtime
The runtime complexity here is since generating all subarrays is a quadratic operation.
-
Memory
The memory usage is since we are using a list to store subarray sums.
— A