Binary search and two-pointer

1498. Number of Subsequences That Satisfy the Given Sum Condition

Bisect solution

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        res = 0
        idx = len(nums)
        def my_bisect(l,r, a):
            while l<r:
                m = (l+r)//2
                if nums[m]>a:r = m
                else:l = m+1
            return l
        for i, num in enumerate(nums):
            if 2*num>target:break
            idx = bisect.bisect(nums, target-num) #NO MORE TLE. runtime 6660 ms. The time requirement for python might be changed.
            #idx = my_bisect(i, idx, target-num) #runtime slightly faster 6872 ms
            #idx = my_bisect(i, len(nums), target-num) # runtime 6972 ms
            if idx <= i:continue
            res += 2**(idx-i-1)
        return  res%(10**9+7)

Two pointer solution

From HERE.

class Solution:
    def numSubseq(self, A: List[int], target: int) -> int:
        A.sort()
        i, j = 0, len(A) - 1
        res = 0
        mod = 10**9 + 7
        while i <= j:
            if A[i] + A[j] > target:
                j -= 1
            else:
                res += pow(2, j - i, mod)
                i += 1
        return res % mod

1508. Range Sum of Sorted Subarray Sums

We can solve this problem by using a naive way.

we can look backward

const int MOD = 1e9+7;
class Solution {
public:
    int rangeSum(vector<int>& nums, int n, int left, int right) {
        vector<int> ret;
        for(int i=0;i<n;++i)
        {
            int sum = 0;
            for (int j=i;j>=0;--j)
            {
                sum += nums[j];
                ret.push_back(sum);
            }
        }
        sort(ret.begin(), ret.end());
        //for(auto x:ret) cout<<x;
        int fin_ret = 0;
        for(int i=left-1;i<right;++i)
        {
            fin_ret += ret[i];
            if (fin_ret>MOD)
            {
                fin_ret %= MOD;
            }
        }
        return fin_ret;
    }
};

we can also look forward

const int MOD = 1e9+7;
class Solution {
public:
    int rangeSum(vector<int>& nums, int n, int left, int right) {
        vector<int> ret;
        for(int i=0;i<n;++i)
        {
            int sum = 0;
            for (int j=i;j<n;++j)
            {
                sum += nums[j];
                ret.push_back(sum);
            }
        }
        sort(ret.begin(), ret.end());
        int fin_ret = 0;
        for(int i=left-1;i<right;++i)
        {
            fin_ret += ret[i];
            if (fin_ret>MOD)
            {
                fin_ret %= MOD;
            }
        }
        return fin_ret;
    }
};

However, a two pointer-based binary search solution is available, and you can find the original post from HERE.

class Solution {
public:
#define maxv 100
#define MOD 1000000007
int rangeSum(vector<int>& nums, int n, int left, int right) {
        int ans=(solve(nums,right)-solve(nums,left-1))%MOD;
        if(ans<0)  ans+=MOD;
        return ans;
    }
    
    int solve(vector<int>& v, int position){
     // find the sum of subarrays for that sum is at <=position in the sorted array
        if(position<1)return 0;
        
        int sum=bsearch(v, position);
        int ans=0;
        int s=0;
        int n=v.size();
        
        int count=0;
        
        vector<int> mult_sums(n),prefix_sums(n);
        prefix_sums[0]=v[0];
        mult_sums[0]=v[0];
        for(int i=1;i<n;i++){
            prefix_sums[i]=(prefix_sums[i-1]+v[i])%MOD;
            mult_sums[i]=(mult_sums[i-1]+(i+1)*v[i])%MOD;
        }
            
        for(int start=0,end=0;end<n;end++){
            s+=v[end];
            for(;start<=end&&s>sum;start++)
                s-=v[start];
            
            count+=end-start+1;
            
            if(start<=end){
                ans+=mult_sums[end]-(start==0?0:mult_sums[start-1]);
                if(start>0) ans-=((long) start*(prefix_sums[end]-prefix_sums[start-1]))%MOD;
                ans%=MOD;
            }
        }
        ans-=((long) (count-position)*sum)%MOD;
        ans%=MOD;
        if(ans<0) ans+=MOD;
        
        return ans;
    }
    
    int bsearch(vector<int>& v, int position){
    // return the position-th number in the sorted sequence
        int n=v.size();
        int low=0;
        int high=maxv*n;
        
        while(low<high){
            int mid=(low+high)/2;
if(count_subarary_with_target(v,mid)<position) low=mid+1;
            else high=mid;
        }
        return low;
    }
    
    int count_subarary_with_target(vector<int>& v, int target){
        
        int n=v.size();
        int s=0;
        int count=0;
        for(int start=0,end=0;end<n;end++){
           s+=v[end];
           for(;start<=end&&s>target;start++)
               s-=v[start];
                
           count+=end-start+1;
        }
        return count;
    }
};