[Rust] Using a bit set | 0ms
Approach\nUsing a bit set provides the benefits of $O(1)$ lookup of values that were in banned without the hashing and table resolution overhead of HashSet. Bit
# Approach\nUsing a bit set provides the benefits of $O(1)$ lookup of values that were in `banned` without the hashing and table resolution overhead of `HashSet`. `BitSet` is very fast.\n\n`bset` is populated while iterating over `banned`. Then the numeric range $[1, n]$ is iterated over until `sum` is too large. Numbers in `bset` are skipped.\n\n`count` keeps track of the number of values that were added to `sum`.\n\n# Complexity\n- Time complexity: $O(len(banned) + n)$\n- Space complexity: $O(1)$ \n\n# Code\n```rust []\nimpl Solution {\n    pub fn max_count(banned: Vec<i32>, n: i32, max_sum: i32) -> i32 {\n        let mut bset  = BitSet::new(10_000);\n        let mut sum   = 0;\n        let mut count = 0;\n\n        for num in banned {\n            bset.set(num as usize);\n        }\n\n        for num in 1..=n as usize {\n            if sum + num > max_sum as usize {\n                break;\n            }\n            if !bset.get(num) {\n                count += 1;\n                sum   += num;\n            }\n        }\n        count\n    }\n}\n\nstruct BitSet {\n    bits: Vec<u64>,\n}\n\nimpl BitSet {\n    fn new(max: usize) -> Self {\n        Self { bits: vec![0; (max + 63) / 64] }\n    }\n    fn set(&mut self, num: usize) {\n        self.bits[num / 64] |= 1 << (num % 64);\n    }\n    fn get(&self, num: usize) -> bool {\n        self.bits[num / 64] >> (num % 64) & 1 == 1\n    }\n}\n```
['Rust']