1498. Number of Subsequences That Satisfy the Given Sum Condition

class Solution {
    public int numSubseq(int[] nums, int target) {
        Arrays.sort(nums);
        int mod = 1_000_000_007;
        int result =0;
        int n = nums.length;
        int[] power = new int[n];
        power[0] = 1;
        for(int i=1;i<n;i++){
            power[i] = (power[i-1] * 2) % mod;
        }

        for(int left=0;left<n;left++){
            int right = binarySearch(nums,target- nums[left]) - 1;
            if(right>=left){
                result += power[right - left];
                result %= mod;
            }
        }

        return result;
    }

    private int binarySearch(int[] nums, int value){
        int low = 0, high = nums.length - 1;
        while(low<=high){
            int mid = low + (high - low)/2;
            if(nums[mid]<=value){
                low = mid + 1;
            }
            else{
                high = mid - 1;
            }
        }
        return low;
    }
}

class Solution {
    public int numSubseq(int[] nums, int target) {
        Arrays.sort(nums);
        int mod = 1_000_000_007;
        int result =0;
        int n = nums.length;
        int[] power = new int[n];
        power[0] = 1;
        for(int i=1;i<n;i++){
            power[i] = (power[i-1] * 2) % mod;
        }
        int left = 0 , right = n - 1;

        while(left<=right){
            if(nums[left] + nums[right] <= target){
                result += power[right - left];
                result %= mod;
                left++;
            }
            else{
                right--;
            }
        }

        return result;
    }
}