Question

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.

Answer 1

public class Main {
    static int search(int arr[], int n, int x)
    {
        int i;
        for (i = 0; i < n; i++) {
            if (arr[i] == x) {
                return i;
            }
        }
        return -1;
    }
  
    public static void main(String[] args)
    {
        int arr[] = {1,2,3,4 };
        int x = 30;
        int n = arr.length;
        System.out.printf("%d is present at index %d", x,
                          search(arr, n, x));
    }
}