# Untitled

unknown
plain_text
a year ago
3.2 kB
0
Indexable
Never
```import java.util.AbstractMap;

class Solution {
int largestSubArraySumPossible = 0, smallestSubArraySumPossible = 0;

// Returns count of subarrays that have
// sum <= target and their total sum.
public Map.Entry<Integer, Long> subArraysWithSumLessThanOrEqualTo(int[] nums, int target){

int  countOfSuchSubArrays = 0;
Long totalSum = 0L;
int  windowSum = 0;
/* currSum intially stores sum of all UNIQUE subArrays in CURRENT WINDOW
Note that we dont consider previous ITERATION unique subarrays
in current iteration.

windowSum stores sum of current window only.

Total sum stores sum of all currSums from all iterations.

Once we pass given target, we shrink both currSum and windowSum

Ex:
Iteration 1: Elements {1} -> unique subArrays -> {1}
-> currSum = 1, windowSum = sum(elements(left, right)) = sum(1) = 1
Iteration 2: Elements {1, 2} -> unique subArrays -> {1, 2}, {2}
-> currSum = (1+2)+2 = 5, windowSum = sum(elements(left, right)) = sum(1+2) = 3
Itr 3:  Elements {1, 2, 3} -> unique subArrays -> {3}, {2, 3}, {1, 2, 3}
-> currSum = (3 + (2+3) + (1+2+3)) = 14 */
int currSum = 0;
int n = nums.length;

for (int left = 0, right = 0; right < n; ++right) {
currSum += nums[right] * (right - left + 1);
windowSum += nums[right];
while (windowSum > target) {
currSum -= windowSum;
windowSum -= nums[left++];
}
countOfSuchSubArrays += right - left + 1;
totalSum += currSum;
}
return new AbstractMap.SimpleEntry<>(Integer.valueOf(countOfSuchSubArrays),
Long.valueOf(totalSum));
}

public Long firstKSubarraysSum(int[] nums, int k){
int start = smallestSubArraySumPossible, end = largestSubArraySumPossible;
while(start < end){
int mid = start + (end-start)/2;
if(subArraysWithSumLessThanOrEqualTo(nums, mid).getKey().intValue() < k){
start = mid + 1;
}
else{
end = mid;
}
}
Map.Entry<Integer, Long> map = subArraysWithSumLessThanOrEqualTo(nums, start);

// When count != k, it means there are subarray(s) whose sum is equal to start
Long totalOfFirstKSubarraysSum = map.getValue();
int countOfSuchSubArrs = map.getKey().intValue();
return totalOfFirstKSubarraysSum - start * (countOfSuchSubArrs - k);
}

public int rangeSum(int[] nums, int n, int left, int right) {
int mod = (int) 1e9 + 7;
int ans = 0;
smallestSubArraySumPossible = nums[0];

for(int i=0; i<n; i++){
largestSubArraySumPossible+=nums[i];
smallestSubArraySumPossible = Math.min(smallestSubArraySumPossible, nums[i]);
}

ans = (int)((firstKSubarraysSum(nums, right) % mod) -
(firstKSubarraysSum(nums, left-1) % mod));

return ans%mod;
}
}```