
Data Structure
Networking
RDBMS
Operating System
Java
MS Excel
iOS
HTML
CSS
Android
Python
C Programming
C++
C#
MongoDB
MySQL
Javascript
PHP
- Selected Reading
- UPSC IAS Exams Notes
- Developer's Best Practices
- Questions and Answers
- Effective Resume Writing
- HR Interview Questions
- Computer Glossary
- Who is Who
Count of Range Sum in C++
Suppose we have an integer array nums, we have to find the number of range sums that lie in range [lower, upper] both inclusive. The range sum S(i, j) is defined as the sum of the elements in nums from index i to index j where i ≤ j.
So if the input is like [-3,6,-1], lower = -2 and upper = 2, then the result will be 2, as the ranges are [0,2], the sum is 2, [2,2], sum is -2.
To solve this, we will follow these steps −
- Define a function mergeIt(), this will take array prefix, start, mid, end, lower, upper,
- i := start, j := mid + 1
- temp := end - start + 1
- low := mid + 1, high := mid + 1
- k := 0
- Define an array arr of size: temp.
- while i <= mid, do −
- while (low <= end and prefix[low] - prefix[i] < lower), do −
- increase low by 1
- while (high <= end and prefix[high] - prefix[i] <= upper), do −
- increase high by 1
- while (j <= end and prefix[j] < prefix[i]), do −
- arr[k] := prefix[j]
- (increase j by 1)
- (increase k by 1)
- arr[k] := prefix[i]
- (increase i by 1)
- (increase k by 1)
- count := count + high - low
- while (low <= end and prefix[low] - prefix[i] < lower), do −
- while j <= end, do −
- arr[k] := prefix[j]
- (increase k by 1)
- (increase j by 1)
- for initialize i := 0, when i < temp, update (increase i by 1), do −
- prefix[start] := arr[i]
- (increase start by 1)
- Define a function merge(), this will take prefix[], start, end, lower, upper,
- if start >= end, then return
- mid := start + (end - start)
- call the function merge(prefix, start, mid, lower, upper)
- call the function merge(prefix, mid + 1, end, lower, upper)
- call the function mergeIt(prefix, start, mid, end, lower, upper)
- From the main method, do the following −
- n := size of nums
- count := 0
- Define an array prefix of size: n+1.
- prefix[0] := 0
- for initialize i := 1, when i <= n, update (increase i by 1), do −
- prefix[i] := prefix[i - 1] + nums[i - 1]
- call the function merge(prefix, 0, n, lower, upper)
- return count
Let us see the following implementation to get better understanding −
Example
#include <bits/stdc++.h> using namespace std; typedef long long int lli; class Solution { public: int count = 0; void mergeIt(lli prefix[], lli start ,lli mid, lli end, lli lower, lli upper){ lli i = start, j = mid + 1; lli temp = end - start + 1; lli low = mid + 1, high = mid + 1; lli k = 0; lli arr[temp]; while(i <= mid){ while(low <= end && prefix[low] - prefix[i] < lower) low++; while(high <= end && prefix[high] - prefix[i] <= upper) high++; while(j<= end && prefix[j] < prefix[i]){ arr[k] = prefix[j]; j++; k++; } arr[k] = prefix[i]; i++; k++; count += high - low; } while(j <= end){ arr[k] = prefix[j]; k++; j++; } for(i = 0; i < temp; i++){ prefix[start] = arr[i]; start++; } } void merge(lli prefix[], lli start, lli end, lli lower, lli upper){ if(start >= end)return; lli mid = start + (end - start) / 2; merge(prefix, start, mid, lower, upper); merge(prefix, mid + 1, end, lower, upper); mergeIt(prefix, start, mid, end, lower, upper); } int countRangeSum(vector<int>& nums, int lower, int upper) { lli n = nums.size(); count = 0; lli prefix[n + 1]; prefix[0] = 0; for(lli i = 1; i <= n; i++){ prefix[i] = prefix[i - 1] + nums[i - 1]; } merge(prefix, 0, n, lower, upper); return count; } }; main(){ Solution ob; vector<int> v = {-3,6,-1}; cout << (ob.countRangeSum(v, -2, 2)); }
Input
{-3,6,-1} -2 2
Output
2
Advertisements