-
Notifications
You must be signed in to change notification settings - Fork 2
/
q1498.swift
97 lines (95 loc) · 2.38 KB
/
q1498.swift
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
//
// q1498.swift
// LeetcodeSwift
//
// Created by NowOrNever on 29/06/2020.
// Copyright © 2020 DL. All rights reserved.
//
import Foundation
//1498. Number of Subsequences That Satisfy the Given Sum Condition
//Medium
//
//86
//
//2
//
//Add to List
//
//Share
//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
//Accepted
//2,262
//Submissions
//7,064
class q1498Solution {
func numSubseq(_ nums: [Int], _ target: Int) -> Int {
var result = 0
let factor = 1000000007
let nums = nums.sorted()
var left = 0
var right = nums.count - 1
var dp = [Int].init(repeating: 0, count: nums.count + 1)
dp[0] = 1
for i in 1..<nums.count {
dp[i] = (dp[i - 1] << 1) % factor
}
while left <= right {
if nums[left] * 2 > target {
break
}
while right > left && nums[right] + nums[left] > target {
right -= 1
}
result = (result + dp[right - left]) % factor
left += 1
}
return result
}
}
func q1498(){
let solu = q1498Solution()
let nums = [5,2,4,1,7,6,8]
let target = 16
let result = solu.numSubseq(nums, target)
print(result)
}