top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

Given an array and query ranges to get sum of each range.

+1 vote
345 views

I have an array suppose A={10,20,30,40,50} and query ranges like 1. 1 4 ie sum of (10+20+30+40) 1 to 4 elements of array and so on.
I tried to solve using brute force method simply
1. Input Array and Query ranges
2. foreach range L to R from Array
a. retrieve elements from array
b. store their sum
3. print sum
but this method has complexity of O( numberOfElementsInArray * SizeOfRange) ie O(mn). Is their any better solution exists ?

posted Oct 25, 2016 by anonymous

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

1 Answer

–1 vote

Hi,
I am just sharing my view on this, you have mentioned that it's complexity is O(mn), but it's not.

As Input to you as a query is Range of indices (Start Index, End Index)
So the sum you can get easily by

for(i = startIndex-1 ; i < EndIndex; i++)
{
sum = sum + arr[i];
}

Which is linear complexities O(N), where N = EndIndex - StartIndex, and in case of worst case N can be equal to number of element in the array.

Share your view on this.

answer Dec 15, 2016 by Sachidananda Sahu
time limit is one second and for the ranges like 1 to 10^9 it is not a good approach. you are doing brute force @sachidananda
ques is not like given an array and a query range .. but there are so many ranges like
array = 1,2,3,4,5,6,.........
query ranges like: 1-5
2-10
100-10000000
**********-1000000000000
Similar Questions
0 votes

Given an unordered array A of size n and integer x. What is the best complexity to find two elements in A whose sum is x?
Share the algo, its complexity and if possible C code.

+2 votes

consider an example :
if an array is: 2 -1 2 4 6 -5
then maximum sum of contiguous array is 13, from index 0 to index 4
constraints: complexity must not be greater than O(n).

+3 votes

Input: arr[] = {5, 5, 10, -10, -20, 40, 50, 35, -20, -50}
Output: 125 (40, 50, 35)

...