🔥💯Day Question 6️⃣ Dec | Simple and clean code | → Without using unordered_set
Intuition\n\nCheck submission..\n\nhttps://leetcode.com/problems/maximum-number-of-integers-to-choose-from-a-range-i/submissions/1471911326\n#### 1. Use a Vecto
# Intuition\n\nCheck submission..\n\n[https://leetcode.com/problems/maximum-number-of-integers-to-choose-from-a-range-i/submissions/1471911326]()\n#### 1. **Use a Vector to Track Banned Numbers**\n   - To efficiently check if a number is banned, a `vector<int>` of size \\(n+1\\) is used. \n   - The index of the vector represents the number, and its value indicates whether the number is banned (`1` for banned, `0` otherwise).\n   - For each number in the `banned` list:\n     - If the number is within the range \\([1, n]\\), mark it as banned by setting `vec[v] = 1`.\n\n   **Why this is efficient**: Lookup in a vector is \\(O(1)\\), making it faster than iterating over the `banned` array repeatedly.\n\n---\n\n#### 2. **Iterate Through the Range [1, n]**\n   - Traverse all integers in the range \\([1, n]\\).\n   - For each integer `i`:\n     - Skip it if it is banned (i.e., `vec[i] == 1`).\n     - Check if adding it to the current sum (`sum`) would keep the total within `maxSum`.\n     - If both conditions are satisfied:\n       - Add the number to the sum.\n       - Increment the count of chosen numbers (`cnt`).\n\n   **Why this is efficient**: The loop iterates only once through \\([1, n]\\), and the operations within the loop (lookup and arithmetic) are \\(O(1)\\).\n\n---\n\n#### 3. **Return the Result**\n   - Once the loop completes, return the count of valid integers (`cnt`) that can be chosen.\n\n---\n\n### **Key Observations**\n- **Efficient Ban Handling**: Using a vector of size \\(n+1\\) avoids repeated lookups in the `banned` array, reducing overhead.\n- **Range-Driven Logic**: The approach iterates directly through the range \\([1, n]\\), ensuring that all valid numbers are considered once.\n\n---\n\n### **Example Walkthrough**\n#### Input:\n- `banned = [2, 4]`, `n = 5`, `maxSum = 8`\n\n#### Steps:\n1. **Mark Banned Numbers**:\n   - Initialize `vec = [0, 0, 0, 0, 0, 0]` (size \\(n+1\\)).\n   - Mark `vec[2] = 1` and `vec[4] = 1`.\n   - Updated `vec`: `[0, 0, 1, 0, 1, 0]`.\n\n2. **Iterate Through Range [1, 5]**:\n   - Start with `sum = 0`, `cnt = 0`.\n   - \\(i = 1\\): Not banned, \\(sum + 1 = 1 \\leq 8\\), choose it (`cnt = 1`, `sum = 1`).\n   - \\(i = 2\\): Banned (`vec[2] = 1`), skip.\n   - \\(i = 3\\): Not banned, \\(sum + 3 = 4 \\leq 8\\), choose it (`cnt = 2`, `sum = 4`).\n   - \\(i = 4\\): Banned (`vec[4] = 1`), skip.\n   - \\(i = 5\\): Not banned, \\(sum + 5 = 9 > 8\\), skip.\n\n3. **Result**:\n   - Maximum numbers chosen: `cnt = 2`.\n\n#### Output:\n`2`\n\n---\n\n### **Complexity**\n- **Time Complexity**: \\(O(m + n)\\), where \\(m\\) is the size of `banned`, and \\(n\\) is the range upper limit.\n- **Space Complexity**: \\(O(n)\\), for the vector used to track banned numbers.\n\nThis approach efficiently handles the constraints, ensuring fast lookups and processing.\n# Code\n```cpp []\nclass Solution {\npublic:\n    int maxCount(vector<int>& banned, int n, int maxSum) {\n\n        vector<int> vec(n + 1, 0);\n        for (const auto& v: banned) {\n            if (v <= n) vec[v] = 1;\n        }\n\n\n        int cnt = 0;\n        long long sum = 0;\n\n        for (int i = 1; i < n + 1; i ++) {\n            if (!(vec[i]) && (sum + i) <= maxSum) {\n                cnt++;\n                sum += i;\n            }\n        }\n\n        return cnt;\n    }\n};\n```\n``` python3 []\nclass Solution:\n    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:\n        lst = [0] * (n + 1)\n\n        for v in banned:\n            if v < n:\n                lst[v] = 1\n\n        cnt = 0\n        som = 0\n\n        for i in range(1, n + 1):\n            \n            if not lst[i] and som + i <= maxSum:\n                som += i\n                cnt += 1\n\n        return cnt \n\n\n```\n[[]()]()\n\nIf you like This approach please upvote....\n\n
['Array', 'C++', 'Python3']