Longest Subsequence With Limited Sum

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

import "sort"

func answerQueries(nums []int, queries []int) []int {
    sort.Ints(nums)
    n := len(nums)
    pref := make([]int, n+1)
    for i := 0; i < n; i++ {
        pref[i+1] = pref[i] + nums[i]
    }
    ans := make([]int, len(queries))
    for i, q := range queries {
        // first index where pref > q; subtract 1
        ans[i] = sort.SearchInts(pref, q+1) - 1
    }
    return ans
}

from bisect import bisect_right
from itertools import accumulate
from typing import List

class Solution:
    def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:
        nums.sort()
        pref = [0] + list(accumulate(nums))
        ans = []
        for q in queries:
            # bisect_right finds first index where pref > q; subtract 1
            ans.append(bisect_right(pref, q) - 1)
        return ans

function answerQueries(nums, queries) {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    const pref = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) pref[i + 1] = pref[i] + nums[i];
    // upper_bound: first index where pref > q
    const upperBound = (q) => {
        let lo = 0, hi = pref.length;
        while (lo < hi) {
            const mid = (lo + hi) >> 1;
            if (pref[mid] <= q) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    };
    return queries.map(q => upperBound(q) - 1);
}

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

    private int upperBound(long[] pref, long q) {
        int lo = 0, hi = pref.length;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (pref[mid] <= q) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }
}

function answerQueries(nums: number[], queries: number[]): number[] {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    const pref: number[] = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) pref[i + 1] = pref[i] + nums[i];
    // upper_bound: first index where pref > q
    const upperBound = (q: number): number => {
        let lo = 0, hi = pref.length;
        while (lo < hi) {
            const mid = (lo + hi) >> 1;
            if (pref[mid] <= q) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    };
    return queries.map(q => upperBound(q) - 1);
}