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

1498. Number of Subsequences That Satisfy the Given Sum Condition

---

the third one in Weekly Contest 195.

---

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 minimum and maximum element on it is less or equal than target.

Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: nums = [3,5,6,7], target = 9
Output: 4
Explanation: There are 4 subsequences that satisfy the condition.
[3] -> Min value + max value <= target (3 + 3 <= 9)
[3,5] -> (3 + 5 <= 9)
[3,5,6] -> (3 + 6 <= 9)
[3,6] -> (3 + 6 <= 9)

Example 2:

Input: nums = [3,3,6,8], target = 10
Output: 6
Explanation: There are 6 subsequences that satisfy the condition. (nums can have repeated numbers).
[3] , [3] , [3,3], [3,6] , [3,6] , [3,3,6]

Example 3:

Input: nums = [2,3,3,4,6,7], target = 12
Output: 61
Explanation: There are 63 non-empty subsequences, two of them don't satisfy the condition ([6,7], [7]).
Number of valid subsequences (63 - 2 = 61).

Example 4:

Input: nums = [5,2,4,1,7,6,8], target = 16
Output: 127
Explanation: All non-empty subset satisfy the condition (2^7 - 1) = 127

Constraints:

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^6
• 1 <= target <= 10^6

---

set a.length = n set's subset count is 2^n set.s no null subset count is 2^n - 1

Solution

• mine
  • Java
    • got from the most votes

      //O(N*logN)time O(N)space → arrays.sort
      public int numSubseq(int[] nums, int target) {
          Arrays.sort(nums);
          int mod = 1000000007;
          int len = nums.length;
          //when set.length = n, count[n] is the subset count
          int[] count = new int[len];
          count[0] = 1;
          for (int i = 1; i < len; i++) {
              //calculate subset count for set.length = i 
              count[i] = (count[i - 1] << 1) % mod;
          }
          int res = 0;
          if (nums[len - 1] * 2 <= target) {
              return ((count[len - 1] << 1) - 1) % mod;
          }
          int l = 0, r = len - 1;
          while (l <= r) {
              //[3,3,6,8]
              //l = 0 → 3 [3,6]  2^2
              //l = 1 → 3 [6] 2^1
              // count = 2^2 + 2^1 = 6
              if (nums[l] + nums[r] > target) {
                  r--;
              } else {
                  res = (res + count[r - l]) % mod;
                  l++;
              }
          }
          return res;
      }
      

---

• the most votes
  • Runtime: 27 ms, faster than 100.00%, Memory Usage: 48.2 MB, less than 100.00% of Java online submissions

    //O(N*logN)time O(N)space
    public int numSubseq(int[] A, int target) {
        Arrays.sort(A);
        int res = 0, n = A.length, l = 0, r = n - 1, mod = (int)1e9 + 7;
        int[] pows = new int[n];
        pows[0] = 1;
        for (int i = 1 ; i < n ; ++i)
            pows[i] = pows[i - 1] * 2 % mod;
        while (l <= r) {
            if (A[l] + A[r] > target) {
                r--;
            } else {
                res = (res + pows[r - l++]) % mod;
            }
        }
        return res;
    }
    

---