Input: banned =[1,6,5], n =5, maxSum =6Output: 2Explanation: 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 is6, which did not exceed maxSum.
Input: banned =[11], n =7, maxSum =50Output: 7Explanation: 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 is28, which did not exceed maxSum.
classSolution {
publicintmaxCount(int[] banned, int n, int maxSum) {
Set<Integer> bannedSet =new HashSet<>();
for (int num : banned) {
bannedSet.add(num);
}
int currSum = 0;
int ans = 0;
for (int i = 1; i <= n; i++) {
if (bannedSet.contains(i)) {
continue;
}
if (currSum + i > maxSum) {
break;
}
currSum += i;
ans++;
}
return ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
classSolution:
defmaxCount(self, banned: List[int], n: int, maxSum: int) -> int:
banned_set: Set[int] = set(banned)
curr_sum: int =0 ans: int =0for i in range(1, n +1):
if i in banned_set:
continueif curr_sum + i > maxSum:
break curr_sum += i
ans +=1return ans
⏰ Time complexity: O(n + m), where n is the range up to n and m is the size of the banned array. Converting the banned array to a set takes O(m), and iterating through the range is O(n).
🧺 Space complexity: O(m) for the set used to store banned elements.