Number of Subsequences That Satisfy the Given Sum Condition LeetCode solution

Problem Statement

Number of Subsequences That Satisfy the Given Sum Condition LeetCode solution – says that Given an array of integers nums and an integer target.

Return the number of non-empty subsequences  nums such that the sum of the minimum and maximum element on it is less or equal to target. Since the answer may be too large, return it modulo 10⁹ + 7.

Example 1:

Input:

 nums = [3,5,6,7], target = 9

Output:

 4

Explanation:

 There are 4 subsequences that satisfy the condition.
[3] -> Min value + max value <= target (3 + 3 <= 9)
[3,5] -> (3 + 5 <= 9)
[3,5,6] -> (3 + 6 <= 9)
[3,6] -> (3 + 6 <= 9)

Approach:

1. We will sort the array.

2. We will find the extreme right position for a fixed index such that our predicate (nums[i]+nums[mid]<=target)is true by performing a binary search

3. So, the length will be len=mid-i+1.

4.Number of subsequence will be (2^len-1)-(2^(len-1)-1)=(2^(len-1)). We will sum up this for every index i.

5. For calculating the power, we can use matrix exponentiation.

C++ Leetcode Solution:

class Solution {
public:
    #define ll long long
    ll mod=1e9+7;
    
    
    int pow(long long x, unsigned int y, int p)
{
    int res = 1;     
 
    x = x % p; 
  
    if (x == 0) 
    return 0;
    while (y > 0)
    {
       
        if (y & 1)
        res = (res*x) % p;
        y = y>>1; 
        x = (x*x) % p;
    }
    return res;
}
    int numSubseq(vector<int>& nums, int target) {
        ll n=nums.size();
        ll i;
        ll sum=0;
        sort(nums.begin(),nums.end());
       for(i=0;i<n;i++)
       {
           ll l=i,r=n-1,mid,ans=-1;
           while(l<=r)
           {
               mid=l+(r-l)/2;
               if(nums[i]+nums[mid]<=target)
               {
                   l=mid+1;
                   ans=mid;
               }
               else
                   r=mid-1;
           }
           if(ans!=-1)
           {
               
               ll len=ans-i+1;
             
               ll yo=pow(2,len,mod);
             
               ll yo1=pow(2,len-1,mod);
               sum+=(yo-yo1);
               sum=sum%mod;
               if(sum<0)sum+=mod;
           }
       }
        return sum;
    }
};

Java Leetcode Solution:

class Solution {
    
     long pow(long x, long y, long p)
  {
    long res = 1; 
 
    x = x % p; 
   
    if (x == 0)
      return 0; 
 
    while (y > 0)
    {
        if ((y & 1) != 0)
        res = (res * x) % p;
 
      y = y >> 1; 
      x = (x * x) % p;
    }
    return res;
  }
 
    public int numSubseq(int[] nums, int target) {
        int n=nums.length,i;
        Arrays.sort(nums);
        long mod=(long)1e9+7;
        long sum=0;
         for(i=0;i<n;i++)
       {
           int l=i,r=n-1,mid,ans=-1;
           while(l<=r)
           {
               mid=l+(r-l)/2;
               if(nums[i]+nums[mid]<=target)
               {
                   l=mid+1;
                   ans=mid;
               }
               else
                   r=mid-1;
           }
           if(ans!=-1)
           {
               
               long len=ans-i+1;
             
               long yo=pow(2,len,mod);
             
               long yo1=pow(2,len-1,mod);
               sum+=(yo-yo1);
               sum=sum%mod;
               if(sum<0)sum+=mod;
           }
             
       }
        
        return (int)sum;
    }
}

Complexity Analysis of Number of Subsequences that satisfy the Given Sum Condition Leetcode Solution:

Time complexity:

O(nlog(n)) is the time complexity. log(n) factor is coming for binary search and we are performing it while traversing the length of the array.

Space complexity:

We are not taking any extra space. So space complexity is O(1).