Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.
Example:
Given nums = [-2, 0, 3, -5, 2, -1] sumRange(0, 2) -> 1 sumRange(2, 5) -> -1 sumRange(0, 5) -> -3
Note:
- You may assume that the array does not change.
- There are many calls to sumRange function.
Approach: Compute the sum till all the ith index in the array for all 0 <= i < n. Use this precomputed values to return the sum.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | class NumArray { public: vector<int> array; vector<int> sum; NumArray(vector<int> &nums) { for(int i = 0 ; i < nums.size(); i++){ array.push_back(nums[i]); } //preProcess after the vector is initialized preProcess(); } //preProcess to store the sum till all i in a vector since the function is called many times void preProcess(){ sum.push_back(0); for(int i = 1; i <= array.size(); i++){ sum.push_back(sum[i - 1] + array[i - 1]); } } int sumRange(int i, int j) { //return sum directly from the calculated sums int res = sum[j + 1] - sum[i]; return res; } }; // Your NumArray object will be instantiated and called as such: // NumArray numArray(nums); // numArray.sumRange(0, 1); // numArray.sumRange(1, 2); |
I did it this way
ReplyDelete#include
using namespace std;
Int main ()
{ int i,j;
int are[10]={6,9,7,4,3,2,9,5,3,5};
int sum =0;
cout< "enter range i and j";
cin>>i;
con>>j;
for(int a =i-1;a<j;a++)
{ sum = sum + art[a];}
cout<<sum<<endl;
return 0;
}
Hi Mr. Ashutosh,
DeleteYour solution will work but it is mentioned that there are many calls to the same function so that gives us a clue that we need to preprocess and store the result so that we can do it in O(1) time excluding the preprocessing.