Solution For Number Of Subsequences That Satisfy The Given Sum Condition

Problem Statement:

Given an array of integers nums and an integer target.

Return the number of non-empty subsequences of nums such that the sum of the elements of the subsequence is equal to target.

A subsequence is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements.

Solution:

To solve this problem, we can use the Two-Pointer algorithm. First, we sort the given array nums in non-decreasing order. Then, we initialize two pointers left and right.

We start with both the pointers at the beginning of the array. We move the right pointer to the end of the array while the sum of the elements between the left and right pointer is less than or equal to the target. Each time we move the right pointer, we calculate the number of subsequences that satisfy the given sum condition.

If the sum of the elements between left and right is greater than the target, we move the left pointer to the next index and repeat the above process until we reach the end of the array.

The number of subsequences that satisfy the given sum condition can be calculated as 2^(count) – 1, where count is the number of elements between left and right.

The base case for this algorithm is when the left pointer and the right pointer both point to the beginning of the array. In this case, we initialize the count variable to 1 and return it as the answer. This is because the empty subsequence is also counted as a valid subsequence.

Time Complexity:

The time complexity of this algorithm is O(nlogn) because we sort the given array before applying the Two-Pointer algorithm, which takes O(nlogn) time.

Space Complexity:

The space complexity of this algorithm is O(1) because we are not using any data structure to store intermediate values.

Code:

class Solution:
def numSubseq(self, nums: List[int], target: int) -> int:
nums.sort()
left, right = 0, len(nums) - 1
count = 0
while left <= right:
if nums[left] + nums[right] <= target:
count += 1 << (right - left)
left += 1
else:
right -= 1
return count % (10 ** 9 + 7)

Explanation:

In the above code, we have defined a function numSubseq that takes an array nums and an integer target as input.

First, we sort the array nums in non-decreasing order using the sort() function.

Next, we initialize two pointers left and right to the beginning and end of the array respectively. We also initialize a variable count to 0.

We then apply the Two-Pointer algorithm as explained above. If the sum of the elements between left and right is less than or equal to the target, we increment the count variable by 2^(right – left). We use the left shift operator to calculate the power of 2.

After applying the Two-Pointer algorithm, we return the count modulo 10^9 + 7 as the answer. This is because the answer can be very large and we need to return it modulo 10^9 + 7 as per the problem statement.

Step by Step Implementation For Number Of Subsequences That Satisfy The Given Sum Condition

public int numSubseq(int[] nums, int target) {
        // sort the array
        Arrays.sort(nums);
        
        // initialize the answer
        int ans = 0;
        
        // compute the answer
        for (int i = 0; i < nums.length; i++) {
            int j = binarySearch(nums, target - nums[i]);
            if (j != -1) {
                ans += (1 << (j - i));
            }
        }
        
        // return the answer
        return ans;
    }
    
    public int binarySearch(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return left - 1;
    }

def numSubseq(nums, target): 

# Initialize answer 

ans = 0

# Sort the array 

nums.sort() 

# Find number of subsequences 

# with sum less than equal 

# to target by including 

# and excluding every element 

for i in range(len(nums)): 

# If nums[i] > target, then 

# all further subsequences 

# will have sum more than target 

# so break the loop 

if (nums[i] > target): 

break

# Find number of subsequences 

# with sum less than equal to 

# target by including nums[i] 

# If nums[j] > target-nums[i], 

# then all further j's will 

# have sum more than target 

# so no need to process further 

for j in range(i, len(nums)): 

if (nums[j] > target - nums[i]): 

break

# Include nums[j] as part 

# of the solution 

ans += 1 << (j - i) 

# Remove nums[j] from 

# the solution 

ans -= 1

# Return the final answer 

return ans

var numSubseq = function(nums, target) {
    // sort the array in ascending order
    nums.sort((a, b) => a - b);
    
    // initialize two pointers, left and right
    let left = 0;
    let right = nums.length - 1;
    
    // initialize a count variable to keep track of the number of subsequnces that satisfy the given sum condition
    let count = 0;
    
    // iterate while left pointer is less than right pointer
    while (left < right) {
        // if the sum of the elements at the left and right pointers is less than the target sum,
        // this means we can increase the number of subsequnces by adding more elements from the left side
        // since the array is sorted in ascending order, all the elements to the right of the current left pointer will satisfy the sum condition
        if (nums[left] + nums[right] < target) {
            // since we can have any number of elements between left and right pointers that satisfy the sum condition,
            // we can increase the count by 2 ^ (right - left - 1)
            count += 2 ** (right - left - 1);
            // move the left pointer to the next element
            left++;
        } else {
            // move the right pointer to the next element
            right--;
        }
    }
    
    // return the count
    return count;
};

int numSubseq(vector& nums, int target) {
    int res = 0, n = nums.size(), l = 0, r = n - 1;
    vector pows(n);
    pows[0] = 1;
    for (int i = 1; i < n; ++i) pows[i] = pows[i - 1] * 2 % MOD;
    sort(nums.begin(), nums.end());
    while (l <= r) {
        if (nums[l] + nums[r] > target) {
            r--;
        } else {
            res = (res + pows[r - l]) % MOD;
            l++;
        }
    }
    return res;
}

public int NumSubseq(int[] nums, int target) {
        // Sort the input array
        Array.Sort(nums);
        
        // Initialize an empty list
        List list = new List();
        
        // Loop through each element in the array
        foreach(int num in nums)
        {
            // If the current element is less than the target, add it to the list
            if(num < target)
            {
                list.Add(num);
            }
            // If the current element is equal to the target, return 1
            else if(num == target)
            {
                return 1;
            }
            // If the current element is greater than the target, break out of the loop
            else
            {
                break;
            }
        }
        
        // Initialize a counter variable
        int count = 0;
        
        // Loop through the list
        for(int i = 0; i < list.Count; i++)
        {
            // Initialize a sum variable
            int sum = list[i];
            
            // Loop through the remaining elements in the list
            for(int j = i + 1; j < list.Count; j++)
            {
                // Add the next element in the list to the sum
                sum += list[j];
                
                // If the sum is equal to the target, increment the counter
                if(sum == target)
                {
                    count++;
                }
                // If the sum is greater than the target, break out of the loop
                else if(sum > target)
                {
                    break;
                }
            }
        }
        
        // Return the count
        return count;
    }