Medium
You are given an integer array banned
and two integers n
and maxSum
. You are choosing some number of integers following the below rules:
[1, n]
.banned
.maxSum
.Return the maximum number of integers you can choose following the mentioned rules.
Example 1:
Input: banned = [1,6,5], n = 5, maxSum = 6
Output: 2
Explanation:
You can choose the integers 2 and 4.
2 and 4 are from the range [1, 5], both did not appear in banned, and their sum is 6, which did not exceed maxSum.
Example 2:
Input: banned = [1,2,3,4,5,6,7], n = 8, maxSum = 1
Output: 0
Explanation:
You cannot choose any integer while following the mentioned conditions.
Example 3:
Input: banned = [11], n = 7, maxSum = 50
Output: 7
Explanation:
You can choose the integers 1, 2, 3, 4, 5, 6, and 7. They are from the range [1, 7], all did not appear in banned, and their sum is 28, which did not exceed maxSum.
Constraints:
1 <= banned.length <= 104
1 <= banned[i], n <= 104
1 <= maxSum <= 109
class Solution {
fun maxCount(banned: IntArray, n: Int, maxSum: Int): Int {
val ban = BooleanArray(20000)
var count = 0
var sum = 0
for (i in banned) ban[i] = true
for (i in 1..n) {
if (ban[i]) {
continue
} else if (sum + i <= maxSum) {
sum += i
count++
} else {
break
}
}
return count
}
}