thảo luận Leetcode mỗi ngày

class Solution:
    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:
        n += 1
        banned = set(banned)
        result, s, i = 0, 0, 1
        while i < n:
            if i + s > maxSum:
                break
            if not i in banned:
                result += 1
                s += i
            i += 1
        return result

class Solution:
    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:
        banned = set(banned)
        currentSum = 0
        choosen = 0
        for i in range(1, n + 1):
            if i not in banned:
                if currentSum + i > maxSum:
                    break

                choosen += 1
                currentSum += i
        
        return choosen

class Solution {

    /**
     * @param Integer[] $banned
     * @param Integer $n
     * @param Integer $maxSum
     * @return Integer
     */
    function maxCount($banned, $n, $maxSum) {
        $banned = array_flip($banned);

        $ans = 0;
        $sum = 0;
        for ($i=1; $i<=$n; $i++) {
            if (isset($banned[$i])) continue;

            $sum += $i;
            if ($sum > $maxSum) break;

            $ans++;
        }

        return $ans;
    }
}

function maxCount(banned: number[], n: number, m: number): number {
    const set = new Set(banned);
    let res = 0, i = 1;
    for (let i = 1; i <= n; i++) {
        if (set.has(i)) continue;
        if (m - i < 0) return res;
        m-= i, res++
    }   
    return res;
};

class Solution {
    public int maxCount(int[] banned, int n, int maxSum) {
        int ans = 0;
        Arrays.sort(banned);
        for (int i = 1; i <= n; i++) {
            if (binarySearch(banned, i)) continue;
            maxSum -= i;
            if (maxSum < 0) break;
            ans++;
        }
        return ans;
    }

    private boolean binarySearch(int[] arr, int k) {
        int l = 0, r = arr.length - 1;
        while (l <= r) {
            int m = l + (r - l) / 2;
            if (k == arr[m]) return true;
            if (k < arr[m]) r = m - 1;
            else l = m + 1;
        }
        return false;
    }
}

class Solution {
    public int maxCount(int[] banned, int n, int maxSum) {
        int ans = 0;
        Set<Integer> set = new HashSet<>();
        for (int ban : banned) set.add(ban);
        for (int i = 1; i <= n; i++) {
            if (set.contains(i)) continue;
            maxSum -= i;
            if (maxSum < 0) break;
            ans++;
        }
        return ans;
    }
}

class Solution:
    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:
        curr = 0
        res = 0
        banned = set(banned)

        for i in range(1, n + 1):
            if i not in banned:
                curr += i
                res += 1
                if curr > maxSum:
                    res -= 1
                    break
        
        return res

var maxCount = function(banned, n, maxSum) {
    banned.sort((u, v) => u - v);
    let s = 0, ans = 0;
    
    for (let i = 1; i <= n; i++) {
        if (s + i <= maxSum && _.sortedIndexOf(banned, i) < 0) {
            s += i;
            ans++;
        }
    }
    return ans;
};

class Solution {
    public int maxCount(int[] banned, int n, int maxSum) {
        Set<Integer> bannedSet = new HashSet<>();
        for (int num : banned) {
            bannedSet.add(num);
        }

        int res = 0;
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            if (bannedSet.contains(i)) {
                continue;
            }
            if (sum + i > maxSum) {
                return res;
            }

            res++;
            sum += i;
        }

        return res;
    }
}

class Solution {
    public int maxCount(int[] banned, int n, int maxSum) {
        int rs = 0, m[] = new int[10001];
        for (int e : banned) m[e] = 1;
        for (int i = 1; i <= n; i++) if (m[i] == 0 && (maxSum -= i) >= 0) rs++; 
        return rs;
    }
}

class Solution {
    public int maxCount(int[] banned, int n, int maxSum) {
        int ans =0;
        int sum =0;
        boolean[] arr = new boolean[n+1];
        for(int num: banned){
            if(num>n)continue;
            arr[num]=true;
        }
        for(int i =1;i<=n;i++){
            if(arr[i]) continue;
            if(sum+i>maxSum) break;
            sum+=i;
            ans++;
        }
        return ans;
    }
}

class Solution {
    func maxCount(_ banned: [Int], _ n: Int, _ maxSum: Int) -> Int {
        let banned = Set(banned)
        var (remain, maxCount) = (maxSum, 0)
        for num in 1...n {
            if remain < num {
                break
            }
            if !banned.contains(num) {
                remain -= num
                maxCount += 1
            }
        }
        return maxCount
    }
}

class Solution {
    public int maxCount(int[] banned, int n, int maxSum) {
        int sum = 0;
        int count = 0;
        Set<Integer> set = new HashSet<>();
        for(int i = 0;i<banned.length;i++){
            set.add(banned[i]);
        }

        for(int i = 1;i<=n;i++){
            if(!set.contains(i)){
                sum += i;
                if(sum > maxSum){
                    break;
                }
                count++;
            }
        }

        return count;
    }
}

class Solution {
public:
    int maxCount(vector<int>& banned, int n, int maxSum) {
        unordered_map<int, bool> umap;
        for(int i=0; i<banned.size(); i++){
            if(banned[i] <= n) umap[banned[i]] = true;
        }
        int count = 0;
        int sum = 0;
        for(int i=1; i <= n ; i++){
            if(!umap[i]){
                sum += i;
                if(sum > maxSum) return count;
                count++;
            }
        }
        return count;
    }
};

class Solution {
    public int maxCount(int[] banned, int n, int maxSum) {
        Set<Integer> set = new HashSet();
        for(int num:banned){
            set.add(num);
        }
        int[] uniq_banned = new int[set.size()];
        int index =0;
        for(int num:set){
            uniq_banned[index++]=num;
        }
        Arrays.sort(uniq_banned);
        int[] prefix_sum = new int[uniq_banned.length];
        prefix_sum[0]= uniq_banned[0];
        for(int i =1;i<uniq_banned.length;i++){
            prefix_sum[i]= prefix_sum[i-1]+uniq_banned[i];
        }
        int l =1;
        int r = n;
        int ans =0;

        while(l<=r){
            int mid = l+(r-l)/2;
            int sum = ((mid+1)*mid)/2;
            int i=find_boundary(mid, uniq_banned);
            if(i!=-1){
                sum-=prefix_sum[i];
            }
            if(sum<=maxSum){
                ans =mid-(i+1);
                l= mid+1;
            }else{
                r=mid-1;
            }
        }
        return ans;
    }
    public int find_boundary(int num, int[] uniq){
        int res =-1;
        int l=0;
        int r = uniq.length-1;
        while(l<=r){
            int mid = l+(r-l)/2;
            if(uniq[mid]<=num){
                res =mid;
                l=mid+1;
            }else{
                r=mid-1;
            }
        }
        return res;
    }
}

class Solution {
    func maxCount(_ banned: [Int], _ n: Int, _ maxSum: Int) -> Int {
        let setBanned = Set(banned)
        var sum = maxSum
        var count = 0 
        for i in 1...n {
            if setBanned.contains(i) {
                continue
            }

            if i <= sum {
                count += 1
                sum -= i
                if sum <= i {
                    return count
                }
            }
        }

        return count
    }
}

class Solution:
    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:
        numSet = set(banned)
        res, curSum = 0, 0
        for v in range(1, n+1):
            if v in numSet:
                continue
            curSum += v
            if curSum > maxSum:
                break
            res += 1
        return res