LeetCode Ts-2554. Maximum Number of Integers to Choose From a Range I

    AllenLi
    CodingLeetCode Js-ArrayLeetCode Js-Math

    You are given an integer array banned and two integers n and 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.
    The sum of the chosen integers should not exceed maxSum.
    Return the maximum number of integers you can choose following the mentioned rules.

    你定一個整數陣列 banned，以及兩個整數 n 和 maxSum。
你需要依照以下規則選擇一些整數：
- 所選的整數必須在範圍 [1, n] 內。
- 每個整數最多只能被選擇一次。
- 所選的整數不能出現在陣列 banned 中。
- 所選整數的總和不得超過 maxSum。
請回傳在滿足上述條件下，最多能選擇的整數數量。

    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.

    Solution:
    我們可以在遍歷 1 ~ n 數字的過程進行累加 sum 與次數 count，
    然後過濾掉存在 banned [] 裡的數字，
    如果 sum 大於題目給的 maxSum，則回傳累加的次數。

    Code 1: BigO(n)

    function maxCount(banned: number[], n: number, maxSum: number): number {
    const set: Set = new Set(banned);    
    let sum: number = 0;
    let count: number = 0;
    
    for (let i = 1; i <= n; i++) {            
        if (set.has(i)) continue;
        if (sum + i > maxSum) break;
        sum += i;
        count++;
    }     
    return count;
};

    FlowChart:
    Example 1

    Input: banned = [1,6,5], n = 5, maxSum = 6

i = 1, set.has(i): true, sum + i > maxSum: false
i = 2, set.has(i): false, sum + i > maxSum: false, sum 2, count 1
i = 3, set.has(i): false, sum + i > maxSum: false, sum 5, count 2
i = 4, set.has(i): false, sum + i > maxSum: true
return count; // 2

    Example 2

    Input: banned = [1,2,3,4,5,6,7], n = 8, maxSum = 1

i = 1, set.has(i): true, sum + i > maxSum: false
i = 2, set.has(i): true, sum + i > maxSum: true
i = 3, set.has(i): true, sum + i > maxSum: true
i = 4, set.has(i): true, sum + i > maxSum: true
i = 5, set.has(i): true, sum + i > maxSum: true
i = 6, set.has(i): true, sum + i > maxSum: true
i = 7, set.has(i): true, sum + i > maxSum: true
i = 8, set.has(i): false, sum + i > maxSum: true
return count; // 0

    Example 3

    Input: banned = [11], n = 7, maxSum = 50

i = 1, set.has(i): false, sum + i > maxSum: false, sum 1, count 1
i = 2, set.has(i): false, sum + i > maxSum: false, sum 3, count 2
i = 3, set.has(i): false, sum + i > maxSum: false, sum 6, count 3
i = 4, set.has(i): false, sum + i > maxSum: false, sum 10, count 4
i = 5, set.has(i): false, sum + i > maxSum: false, sum 15, count 5
i = 6, set.has(i): false, sum + i > maxSum: false, sum 21, count 6
i = 7, set.has(i): false, sum + i > maxSum: false, sum 28, count 7
return count; // 7

    Related Posts