##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2389.html

# 2389. Longest Subsequence With Limited Sum

• Difficulty: Easy.
• Related Topics: Array, Binary Search, Greedy, Sorting, Prefix Sum.
• Similar Questions: How Many Numbers Are Smaller Than the Current Number, Successful Pairs of Spells and Potions.

## Problem

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

## Solution (Java, C++, Python)

• class Solution {
public int[] answerQueries(int[] nums, int[] queries) {
// we can sort the nums because the order of the subsequence does not matter
Arrays.sort(nums);
for (int i = 1; i < nums.length; i++) {
nums[i] = nums[i] + nums[i - 1];
}
for (int i = 0; i < queries.length; i++) {
int j = Arrays.binarySearch(nums, queries[i]);
if (j < 0) {
j = -j - 2;
}
queries[i] = j + 1;
}
return queries;
}
}

############

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:
def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:
nums.sort()
s = list(accumulate(nums))
return [bisect_right(s, v) for v in queries]

############

# 2389. Longest Subsequence With Limited Sum
# https://leetcode.com/problems/longest-subsequence-with-limited-sum/

class Solution:
def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:
n = len(nums)
nums.sort()
res = []
prefix = list(accumulate(nums, initial = 0))

for q in queries:
index = bisect_right(prefix, q) - 1
res.append(index)

return res


• 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;
}
};

• 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;
}


• 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()
}
}

• 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;
}
}



Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).