[LeetCode][Kotlin] 1498. Number of Subsequences That Satisfy the Given Sum Condition

1498. Number of Subsequences That Satisfy the Given Sum Condition

You are 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 to target. Since the answer may be too large, return it modulo 109 + 7.

정수 nums와 정수 target의 배열이 주어집니다. 

nums의 비어 있지 않은 부분 시퀀스의 개수를 반환합니다. 이 부분 시퀀스의 최소 및 최대 요소의 합은 target보다 작거나 같습니다. 답이 너무 클 수 있으므로 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 do not satisfy the condition ([6,7], [7]).

Number of valid subsequences (63 - 2 = 61).

 

Constraints:

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

---

코드

class Solution {
    fun numSubseq(nums: IntArray, target: Int): Int {
        nums.sort()

        val mod = 1000000000 + 7
        
        val pow = IntArray(nums.size)
        pow[0] = 1
        for (i in 0 until nums.lastIndex) {
            pow[i + 1] = pow[i] * 2 % mod
        }

        var answer = 0
        var left = 0
        var right = nums.lastIndex
        
        while (left <= right) {
            if (nums[left] + nums[right] > target) {
                right--
            } else {
                answer = (answer + pow[right - left]) % mod
                left++
            }
        }

        return answer
    }
}