diff options
-rw-r--r-- | max_num_int_choose_range1.c | 38 | ||||
-rw-r--r-- | max_num_int_choose_range1.py | 35 |
2 files changed, 73 insertions, 0 deletions
diff --git a/max_num_int_choose_range1.c b/max_num_int_choose_range1.c new file mode 100644 index 0000000..c447475 --- /dev/null +++ b/max_num_int_choose_range1.c @@ -0,0 +1,38 @@ +// 2554. Maximum Number of Integers to Choose From a Range I +#include "leetcode.h" + +/* + * you are given an integer array 'banned' and two integers 'n' and a 'maxSum'. + * you are choosing some number of integers following the below rules: the + * chosen integers have to be in the range '[1, n]', each integer can be chosen + * at most once, the chosen integers should not be in the array 'banned', and + * the sum of the chosen ntegers should not exceed 'maxSum'. return the maximum + * number of integers you can choose following the mentioned rules. + */ + +int maxCount(int *banned, int bannedSize, int n, int maxSum) { + bool *valid = (bool *)malloc((n + 1) * sizeof(bool)); + memset(valid + 1, true, n * sizeof(bool)); + for (int i = 0; i < bannedSize; i++) { + if (!(banned[i] >= 1 && banned[i] <= n)) + continue; + valid[banned[i]] = false; + } + int cnt = 0, curr_sum = 0; + for (int i = 1; i <= n; i++) { + if (!valid[i]) + continue; + if (!(curr_sum + i <= maxSum)) + break; + cnt++, curr_sum += i; + } + free(valid); + return cnt; +} + +int main() { + int b1[] = {1, 6, 5}, b2[] = {1, 2, 3, 4, 5, 6, 7}, b3[] = {11}; + printf("%d\n", maxCount(b1, ARRAY_SIZE(b1), 5, 6)); // expect: 2 + printf("%d\n", maxCount(b2, ARRAY_SIZE(b2), 8, 1)); // expect: 0 + printf("%d\n", maxCount(b3, ARRAY_SIZE(b3), 7, 50)); // expect: 7 +} diff --git a/max_num_int_choose_range1.py b/max_num_int_choose_range1.py new file mode 100644 index 0000000..9c6c30c --- /dev/null +++ b/max_num_int_choose_range1.py @@ -0,0 +1,35 @@ +# 2554. Maximum Number of Integers to Choose From a Range I + +""" +you are given an integer array 'banned' and two integers 'n' and a 'maxSum'. +you are choosing some number of integers following the below rules: the +chosen integers have to be in the range '[1, n]', each integer can be chosen +at most once, the chosen integers should not be in the array 'banned', and +the sum of the chosen ntegers should not exceed 'maxSum'. return the maximum +number of integers you can choose following the mentioned rules. +""" + + +class Solution(object): + def maxCount(self, banned, n, maxSum): + """ + :type banned: List[int] + :type n: int + :type maxSum: int + :rtype: int + """ + ans, banned = -1, set(banned) + for i in range(1, n + 1): + if i not in banned: + maxSum -= i + ans += 1 + if maxSum < 0: + return ans + return ans + 1 + + +if __name__ == "__main__": + obj = Solution() + print(obj.maxCount(banned=[1, 6, 5], n=5, maxSum=6)) + print(obj.maxCount(banned=[1, 2, 3, 4, 5, 6, 7], n=8, maxSum=1)) + print(obj.maxCount(banned=[11], n=7, maxSum=50)) |