Answer to Question #216834 in Java | JSP | JSF for rocky

Question

Question 1.

Mickeymouse loves numbers in the range [m1, m2] (m1 and m2 included). Minnie decides to gift Mickey an array of numbers for his birthday. Mickey wants to find the number of pairs of indices [l, r] for which the sum of all the  elements in the range [l, r] lies between m1 and m2.   

1. Come up with an algorithm with a worst case complexity of O(N2).   (5 marks) 
2. Now improvise this algorithm, assuming all numbers are positive integers.    (7 marks)
3. What if the numbers could be negative as well? Can you think of an O(nlogn) solution in this case? (Hint: use sorting)  (10 marks)

Sample case: 

Array = [-2, 5, -1]

M1 = -2

M2 = 2

Output: 3 

[[0, 0], [2, 2], [0, 2]] are the three pairs of [l, r] that satisfy the condition. So, that is why, the output is 3.  

Notes: Recurrence relation not needed in first two parts. But do explain the reason for the resulting time complexity in words. 

Answer 1

1.
start
start_range m_1
end_rangee m_2
gift_range_start l
gif_range_end r

for loop from m_1 to m_2
sum=l+r
if (sum>m_1)
  l++,r++;
if(m_2>sum)
  then break the loop
print the the output range 

2.

start
start_range m_1>0
end_rangee m_2>m_1
gift_range_start l>0
gif_range_end r>l

for loop from m_1 to m_2
sum=l+r
if (sum>m_1)
  l++,r++;
if(m_2>sum)
  then break the loop
print the the output range