Skip to content

1498. Number of Subsequences That Satisfy the Given Sum Condition 👍

  • Time: $O(\texttt{sort})$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
 public:
  int numSubseq(vector<int>& nums, int target) {
    constexpr int kMod = 1'000'000'007;
    const int n = nums.size();
    int ans = 0;
    vector<int> pows(n, 1);  // pows[i] = 2^i % kMod

    for (int i = 1; i < n; ++i)
      pows[i] = pows[i - 1] * 2 % kMod;

    ranges::sort(nums);

    for (int l = 0, r = n - 1; l <= r;)
      if (nums[l] + nums[r] <= target) {
        ans += pows[r - l];
        ans %= kMod;
        ++l;
      } else {
        --r;
      }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
  public int numSubseq(int[] nums, int target) {
    final int kMod = 1_000_000_007;
    final int n = nums.length;
    int ans = 0;
    int[] pows = new int[n]; // pows[i] = 2^i % kMod
    pows[0] = 1;

    for (int i = 1; i < n; ++i)
      pows[i] = pows[i - 1] * 2 % kMod;

    Arrays.sort(nums);

    for (int l = 0, r = n - 1; l <= r;)
      if (nums[l] + nums[r] <= target) {
        ans += pows[r - l];
        ans %= kMod;
        ++l;
      } else {
        --r;
      }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
  def numSubseq(self, nums: List[int], target: int) -> int:
    kMod = 1_000_000_007
    n = len(nums)
    ans = 0

    nums.sort()

    l = 0
    r = n - 1
    while l <= r:
      if nums[l] + nums[r] <= target:
        ans += pow(2, r - l, kMod)
        l += 1
      else:
        r -= 1

    return ans % kMod