Number of Subsequences That Satisfy the Given Sum Condition | Leetcode 1498

class Solution {
    int MOD = 1e9+7;
    void precomputePowerOfTwo(vector<int>& power_of_two,int& n){
        power_of_two[0]=1;
        for(int i=1;i<n;++i)
            power_of_two[i] = (power_of_two[i-1]*2LL)%MOD;
    }
public:
    int numSubseq(vector<int>& nums, int target) {
        int n = nums.size();
        vector<int> power_of_two(n);
        precomputePowerOfTwo(power_of_two,n);
        
        sort(nums.begin(),nums.end());
        int subsequences = 0;

        int left = 0;
        int right = n-1;
        while(left<=right){
            if(nums[left]+nums[right]>target)
                right--;
            else{
                subsequences = (subsequences + power_of_two[right-left])%MOD;
                left++;
            }
        }
        return subsequences;
    }
};
/*
//JAVA
import java.util.Arrays;

class Solution {
    final int MOD = (int)1e9 + 7;
    
    private void precomputePowerOfTwo(int[] powerOfTwo, int n) {
        powerOfTwo[0] = 1;
        for (int i = 1; i < n; ++i) {
            powerOfTwo[i] = (int)((powerOfTwo[i - 1] * 2L) % MOD);
        }
    }
    
    public int numSubseq(int[] nums, int target) {
        int n = nums.length;
        int[] powerOfTwo = new int[n];
        precomputePowerOfTwo(powerOfTwo, n);
        
        Arrays.sort(nums);
        int subsequences = 0;
        
        int left = 0;
        int right = n - 1;
        while (left <= right) {
            if (nums[left] + nums[right] > target) {
                right--;
            } else {
                subsequences = (subsequences + powerOfTwo[right - left]) % MOD;
                left++;
            }
        }
        return subsequences;
    }
}

#Python
class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        MOD = 10**9 + 7
        n = len(nums)
        power_of_two = [1] * n
        for i in range(1, n):
            power_of_two[i] = (power_of_two[i - 1] * 2) % MOD
        
        nums.sort()
        subsequences = 0
        left, right = 0, n - 1
        
        while left <= right:
            if nums[left] + nums[right] > target:
                right -= 1
            else:
                subsequences = (subsequences + power_of_two[right - left]) % MOD
                left += 1
        return subsequences
*/