leetcodedaybyday - Beats 100% with C++ and Beats 96.55% with Python3
IntuitionThe problem requires determining the maximum number of elements from a sorted list of integers (nums) that can sum up to or less than a given value in
# Intuition
The problem requires determining the maximum number of elements from a sorted list of integers (`nums`) that can sum up to or less than a given value in each query. By sorting `nums` and using prefix sums, we can efficiently calculate the result for each query.

# Approach
1. **Sort the Input Array**:
   - Sort `nums` in ascending order so that smaller elements are considered first, maximizing the number of elements that can be included.

2. **Compute Prefix Sums**:
   - Create a prefix sum array where `prefixSum[i]` represents the sum of the first `i` elements in `nums`. This allows constant-time sum calculations for any subset of the array.

3. **Binary Search for Each Query**:
   - Use `std::upper_bound` (C++) or `bisect_right` (Python) on the prefix sum array to find the largest index such that the sum does not exceed the query value. The result is the count of elements for that query.

4. **Return Results**:
   - Collect the results for all queries and return them as a list.

# Complexity
# Complexity
- **Time Complexity**:  
  O(n * log(n) + m * log(n)), where \(n\) is the size of `nums` and \(m\) is the number of queries. Sorting `nums` takes O(n * log(n)), and for each query, binary search takes O(log(n)), making the total time O(m * log(n)) for the queries.

- **Space Complexity**:  
  O(n), for the prefix sum array.

# Code
```cpp []
class Solution {
public:
    vector<int> answerQueries(vector<int>& nums, vector<int>& queries) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<int> prefixSum(n + 1, 0);
        for (int i = 1; i <= n; i++){
            prefixSum[i] = prefixSum[i - 1] + nums[i - 1];
        }
        std::vector<int> answer;
        for (int query : queries){
            int maxIndex = std::upper_bound(prefixSum.begin(), prefixSum.end(), query) - prefixSum.begin() - 1;
            answer.push_back(maxIndex);
        }
        return answer;
    }
};



```
```python3 []
class Solution:
    def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:
        nums.sort()
        n = len(nums)
        prefixSum = [0] * (n + 1)

        for i in range(1, n + 1):
            prefixSum[i] = prefixSum[i - 1] + nums[i - 1]
        res = []
        for query in queries:
            max_idx = bisect_right(prefixSum, query) - 1
            res.append(max_idx)
        return res



```


['Binary Search', 'Prefix Sum', 'C++', 'Python3']