LeetCode Entry

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

06.12.2024 medium 2024 kotlin rust

Sum 1..n excluding banned until maxSum

2554. Maximum Number of Integers to Choose From a Range I medium blog post substack youtube deep-dive

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/824

Problem TLDR

Sum 1..n excluding banned until maxSum #medium

Intuition

• we can use a HashSet
• we can sort and do two pointers
• we can precompute all sums and do a binary search

Approach

• careful with duplicates in the sort solution

Complexity

• Time complexity: \(O(n)\) or O(nlog(n))

• Space complexity: \(O(n)\) or O(1)

Code

    fun maxCount(banned: IntArray, n: Int, maxSum: Int): Int {
        val set = banned.toSet(); var s = 0; var cnt = 0
        for (x in 1..n) if (x !in set) {
            s += x; if (s > maxSum) break; cnt++
        }
        return cnt
    }

    pub fn max_count(mut banned: Vec<i32>, n: i32, max_sum: i32) -> i32 {
        banned.sort_unstable(); let (mut j, mut s, mut cnt) = (0, 0, 0);
        for x in 1..=n {
            if j < banned.len() && x == banned[j] {
                while j < banned.len() && x == banned[j] { j += 1 }
              k
        }; cnt
    }

    int maxCount(vector<int>& banned, int n, int maxSum) {
        int cnt = 0, s = 0; int b[10001] = {};
        for (int x: banned) b[x] = 1;
        for (int x = 1; x <= n && s + x <= maxSum; ++x)
            cnt += 1 - b[x], s += x * (1 - b[x]);
        return cnt;
    }