Skip to content

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

  • Time:
  • Space:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
 public:
  int numSubseq(vector<int>& nums, int target) {
    constexpr int kMod = 1e9 + 7;
    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;

    sort(begin(nums), end(nums));

    for (int l = 0, r = n - 1; l <= r;)
      if (nums[l] + nums[r] <= target) {
        ans = (ans + pows[r - l]) % 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
class Solution {
  public int numSubseq(int[] nums, int target) {
    final int kMod = (int) 1e9 + 7;
    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 = (ans + pows[r - l]) % kMod;
        ++l;
      } else {
        --r;
      }

    return ans;
  }
}
Back to top