Leetcode Problem 1498. Number of Subsequences That Satisfy the Given Sum Condition

1498. Number of Subsequences That Satisfy the Given Sum Condition

Leetcode Solutions

Two Pointers Approach

  1. Sort the array nums in ascending order.
  2. Initialize answer to 0 and mod to 10^9 + 7.
  3. Precompute powers of 2 up to the length of nums and store them in an array power, taking modulo mod.
  4. Set two pointers: left to 0 and right to the length of nums - 1.
  5. Iterate over left from 0 to the length of nums - 1: a. While left is less than or equal to right and the sum of nums[left] and nums[right] is greater than target, decrement right. b. If left is less than or equal to right, add power[right - left] to answer (modulo mod). c. Increment left.
  6. Return answer.
UML Thumbnail

Binary Search Approach

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...