Count of Range Sums

Given an integer array nums, return the number of range sums that lie in [lower, upper] inclusive. Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j (i ≤ j), inclusive. A naïve algorithm of O(n2) is trivial. You MUST do better than that.

Difficulty: Very hard.

Input

The first line contains 3 integers separated by spaces:

  • n, representing the length of the integer array nums.
  • lower.
  • upper.

The second line is the integer array nums, containing n integers with neighboring elements separated by a space.

At the end of each line, there are no extra spaces, and there is a \n.

Output

One line containing 1 integer, which is the number of range sums that lie in [lower, upper] inclusive.

Example

Input:

3 -2 2

-2 5 1

Output:

3

Explanation:

nums = [-2,5,-1], lower = -2, upper = 2.

The three ranges are : [0,0], [2,2], [0,2] and their respective sums are: -2, -1, 2.

Solution: C++

#include<stdlib.h>
#include<stdio.h>
#include<iostream>

using namespace std;

// merge the two ordered arrays b and c into the original array a
void merge(long long int a[], int l, int m, int r){
    int n1 = m - l + 1; //size of array b
    int n2 =  r - m; //size of array c

    // create temp arrays of b and c
    long long int B[n1], C[n2];

    int i, j;
    // copy arrays a and b into temp arrays B and C
    for (i = 0; i < n1; i++)
        B[i] = a[l + i];
    for (j = 0; j < n2; j++)
        C[j] = a[m + 1 + j];

    // merge the temp arrays A and B back into array a in the right position
    i = 0; // index of B
    j = 0; // index of C
    int idx = l; // index of the array a
    while (i < n1 && j < n2){
        if (B[i] <= C[j]){
            a[idx] = B[i];
            i++;
        }
        else{
            a[idx] = C[j];
            j++;
        }
        idx++;
    }

    // copy the remaining elements of B into a
    while (i < n1) {
        a[idx] = B[i];
        i++;
        idx++;
    }

    // copy the remaining elements of C into a
    while (j < n2) {
        a[idx] = C[j];
        j++;
        idx++;
    }
}

int merge_solve(int l, int r, long long int lower, long long int upper, long long int p[]){ //2T(n/2)+O(n)
    if (l < r){
        int m = l+(r-l)/2; //index to split the the array in two parts
        int s1 = merge_solve(l, m, lower, upper, p); //range sums in first half
        int s2 = merge_solve(m+1, r, lower, upper, p); //range sums in second half

        int range_sums=0;
        //j = iterator for second half
        int i1=l; //i1 = iterator upper bound first half
        int i2=l; //i2 = iterator lower bound first half
        // find all (i,j) indexes satisfying the constraints
        for(int j=m+1;j<=r;j++){
            for(;i1<=m && p[i1]+lower<=p[j];i1++);
            for(;i2<=m && p[j]>p[i2]+upper;i2++);
            range_sums+=i1-i2;
        }

        merge(p, l, m, r); //same as mergesort
        return range_sums+s1+s2;
    }
    // l==r
    return lower<=p[l] && p[l]<=upper;
}

int main(){
    int n;
    cin>>n;  //length of the array
    long long int lower; //sum lower bound
    cin>>lower;
    long long int upper; //sum upper bound
    cin>>upper;
    int nums[n];
    for(int i=0; i<n; i++)
        cin>>nums[i];

    long long int p[n];
    p[0]=nums[0];
    for(int i=1;i<n;i++){ //O(n)
        p[i]=p[i-1]+nums[i];
    }

    int n_range_sum = merge_solve(0, n-1, lower, upper, p);
    cout<<n_range_sum;
}

Related posts

One thought on “Count of Range Sums

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s