Similar Problems

Similar Problems not available

Number Of Subsequences That Satisfy The Given Sum Condition - Leetcode Solution

Companies:

LeetCode:  Number Of Subsequences That Satisfy The Given Sum Condition Leetcode Solution

Difficulty: Medium

Topics: sorting two-pointers array binary-search  

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.

Number Of Subsequences That Satisfy The Given Sum Condition Solution Code

1