👉 "💡 Longest Subsequence with Limited Sum | Easy-to-Understand C++ Solution 🌟"
IntuitionThe problem asks us to find the longest subsequence whose sum of elements does not exceed a given value for each query. My initial thought was to use s
# Intuition
The problem asks us to find the longest subsequence whose sum of elements does not exceed a given value for each query. My initial thought was to use sorting and prefix sums, as they would allow efficient computation of cumulative sums. By leveraging binary search, we can quickly determine the maximum number of elements that fit each query constraint.

# Approach
Sort the Array: To ensure we process the smallest elements first (to maximize the subsequence length).
Prefix Sum: Compute cumulative sums of the sorted array to easily calculate the sum of any subsequence starting from the smallest elements.
Binary Search: For each query, use binary search to determine the largest prefix sum that is less than or equal to the query value.
Store Results: Save the length of the subsequence for each query in the result array.

# Complexity
- Time complexity:
Sorting the array takes 
𝑂
(
𝑛
log
⁡
𝑛
)
O(nlogn).
Creating the prefix sum array takes 
𝑂
(
𝑛
)
O(n).
Processing each query with binary search takes 
𝑂
(
𝑚
log
⁡
𝑛
)
O(mlogn).
Thus, the overall complexity is 
𝑂
(
𝑛
log
⁡
𝑛
+
𝑚
log
⁡
𝑛
)
O(nlogn+mlogn).


- Space complexity:
The algorithm uses 
𝑂
(
1
)
O(1) extra space apart from the input and output arrays.

# Code
```cpp []
class Solution {
public:
    vector<int> answerQueries(vector<int>& nums, vector<int>& queries) {
       int n = nums.size();
       int m = queries.size();
       vector<int> ans(m);
       //sort nums
       sort(nums.begin(), nums.end());
       // make nums prefix sum
       for(int i=1;i<n;i++){
        nums[i] +=  nums[i-1];
       } 
       for(int i=0;i<m;i++){  
        int maxlen = 0;
        //binary search
        int lo = 0;
        int hi = n-1;
        while(lo<=hi){
            int mid = lo+(hi-lo)/2;
            if(nums[mid]>queries[i]) hi =mid-1;
            else{  // nums[mid] <= queries[i]
                maxlen = mid+1;
                lo = mid+1;
            }
        }

       
        
            ans[i] = maxlen;
       }
       return ans;
    }
};
```
['Array', 'Binary Search', 'Greedy', 'Sorting', 'Prefix Sum', 'C++']