DDSA
Advertisement

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

Time: O(n)
Space: O(banned)

Approach

HashSet for banned; accumulate integers 1..n skipping banned until maxSum exceeded.

2554.cs
C#
// Approach: HashSet for banned; accumulate integers 1..n skipping banned until maxSum exceeded.
// Time: O(n) Space: O(banned)

public class Solution
{
    public int MaxCount(int[] banned, int n, int maxSum)
    {
        int answerCount = 0;
        int currentSum = 0;
        HashSet<int> bannedNumberSet = new HashSet<int>(banned);

        for (int currentNumber = 1; currentNumber <= n; ++currentNumber)
        {
            if (!bannedNumberSet.Contains(currentNumber) && currentSum + currentNumber <= maxSum)
            {
                ++answerCount;
                currentSum += currentNumber;
            }
        }

        return answerCount;
    }
}
Advertisement
Was this solution helpful?