Answer to Question #215977 in Java | JSP | JSF for Shivanshu

Question

Harry loves numbers in the range [m1, m2] (m1 and m2 included). carry decides to gift harry an array of numbers for his birthday. harry 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).
2. Now improvise this algorithm, assuming all numbers are positive integers.  
3. What if the numbers could be negative as well? Can you think of an O(nlogn) solution in this case? (Hint: use sorting)  

Answer 1

package com.company;

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner cin=new Scanner(System.in);
        System.out.println("Enter m1 and m2");
        int m1=cin.nextInt();
        int m2= cin.nextInt();
        System.out.println("Enter size:");
        int n=cin.nextInt();//Scaner size array
        System.out.println("Please enter numbers");
        int []a=new int[n];
        for(int i=0;i<n;i++)
            a[i]= cin.nextInt();
        int cnt=0;//Count [l,r] pairs
        long []sum=new long[n];
        sum[0]=a[0];
        for(int i=1;i<n;i++)
            sum[i]=sum[i-1]+a[i];
        for(int i=0;i<n;i++)
            System.out.print(sum[i]+" ");
    for(int l=0;l<n;l++)
    {
        for(int r=l;r<n;r++)
        {
            long sm=sum[n-1]-((sum[n-1]-sum[l]+a[l])+(sum[n-1]-sum[r]+a[r]));
            if(sm>=m1&&sm<=m2)
                cnt++;
        }
    }
    System.out.println("Count: "+cnt);
    }


}
// 1 2 3 4 5
// 1 3 6 10 15