# 2389. Longest Subsequence With Limited Sum

## Description

You are given an integer array nums of length n, and an integer array queries of length m.

Return an array answer of length m where answer[i] is the maximum size of a subsequence that you can take from nums such that the sum of its elements is less than or equal to queries[i].

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

Example 1:

Input: nums = [4,5,2,1], queries = [3,10,21]
Output: [2,3,4]
Explanation: We answer the queries as follows:
- The subsequence [2,1] has a sum less than or equal to 3. It can be proven that 2 is the maximum size of such a subsequence, so answer[0] = 2.
- The subsequence [4,5,1] has a sum less than or equal to 10. It can be proven that 3 is the maximum size of such a subsequence, so answer[1] = 3.
- The subsequence [4,5,2,1] has a sum less than or equal to 21. It can be proven that 4 is the maximum size of such a subsequence, so answer[2] = 4.


Example 2:

Input: nums = [2,3,4,5], queries = [1]
Output: [0]
Explanation: The empty subsequence is the only subsequence that has a sum less than or equal to 1, so answer[0] = 0.

Constraints:

• n == nums.length
• m == queries.length
• 1 <= n, m <= 1000
• 1 <= nums[i], queries[i] <= 106

## Solutions

• class Solution {
public int[] answerQueries(int[] nums, int[] queries) {
Arrays.sort(nums);
for (int i = 1; i < nums.length; ++i) {
nums[i] += nums[i - 1];
}
int m = queries.length;
int[] ans = new int[m];
for (int i = 0; i < m; ++i) {
ans[i] = search(nums, queries[i]);
}
return ans;
}

private int search(int[] nums, int x) {
int l = 0, r = nums.length;
while (l < r) {
int mid = (l + r) >> 1;
if (nums[mid] > x) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}
}

• class Solution {
public:
vector<int> answerQueries(vector<int>& nums, vector<int>& queries) {
sort(nums.begin(), nums.end());
for (int i = 1; i < nums.size(); i++) {
nums[i] += nums[i - 1];
}
vector<int> ans;
for (auto& q : queries) {
ans.push_back(upper_bound(nums.begin(), nums.end(), q) - nums.begin());
}
return ans;
}
};

• class Solution:
def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:
nums.sort()
s = list(accumulate(nums))
return [bisect_right(s, q) for q in queries]


• func answerQueries(nums []int, queries []int) (ans []int) {
sort.Ints(nums)
for i := 1; i < len(nums); i++ {
nums[i] += nums[i-1]
}
for _, q := range queries {
ans = append(ans, sort.SearchInts(nums, q+1))
}
return
}

• function answerQueries(nums: number[], queries: number[]): number[] {
nums.sort((a, b) => a - b);
for (let i = 1; i < nums.length; i++) {
nums[i] += nums[i - 1];
}
const ans: number[] = [];
const search = (nums: number[], x: number) => {
let l = 0;
let r = nums.length;
while (l < r) {
const mid = (l + r) >> 1;
if (nums[mid] > x) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
};
for (const q of queries) {
ans.push(search(nums, q));
}
return ans;
}


• public class Solution {
public int[] AnswerQueries(int[] nums, int[] queries) {
int[] result = new int[queries.Length];
Array.Sort(nums);
for (int i = 0; i < queries.Length; i++) {
result[i] = getSubsequent(nums, queries[i]);
}
return result;

}

public int getSubsequent(int[] nums,int query) {
int sum = 0;
for (int i = 0; i < nums.Length; i++) {
sum += nums[i];
if (sum > query) {
return i;
}
}
return nums.Length;
}
}


• impl Solution {
pub fn answer_queries(mut nums: Vec<i32>, queries: Vec<i32>) -> Vec<i32> {
let n = nums.len();
nums.sort();
queries
.into_iter()
.map(|query| {
let mut sum = 0;
for i in 0..n {
sum += nums[i];
if sum > query {
return i as i32;
}
}
n as i32
})
.collect()
}
}