sort and count, java
Easy Method: O(n^2) - Accepted\nsort the array. (don\'t worry about subsequence, we only care about the sum)\ncount how many numbers you can pick for each query
**Easy Method:** *O(n^2) - Accepted*\nsort the array. (don\'t worry about subsequence, we only care about the sum)\ncount how many numbers you can pick for each query.\n\n\n    public int[] answerQueries(int[] nums, int[] q) {\n        Arrays.sort(nums);\n\t\tint[] res = new int[q.length];\n        for(int i = 0; i<q.length; i++) {\n            int sum = 0, j = 0;\n            for(j=0; j<nums.length; j++) {\n                if(sum+nums[j]>q[i]){\n                    res[i] = j;\n                    break;\n                }\n                sum = sum+nums[j];\n            }\n            if(j==nums.length) res[i] = j;\n        }\n        return res;\n    }\n\t\n---\n\t\n**Optimized:** *O(nlogn)*\nwe can use prefix sum and find the closest index using binary search.\n\n    public int[] answerQueries(int[] nums, int[] q) {\n\t\tint[] res = new int[q.length];\n        \n\t\tArrays.sort(nums);\n        for(int i=1; i<nums.length; i++)      // calculate prefix\n            nums[i] = nums[i] + nums[i-1];\n        \n        for(int i=0; i<q.length; i++)       // search and build res\n            res[i] = search(nums, q[i]);\n        \n        return res;\n    }\n    \n    int search(int[] nums, int find){\n        int left = 0, right = nums.length-1;\n        while(left<right){\n            int mid = left+(right-left)/2;\n            if(nums[mid]==find) return mid+1;\n            if(nums[mid]<find) left = mid+1;\n            else right = mid;\n        }\n        return nums[left]<=find ? left+1: left;\n    }
['Sorting', 'Binary Tree', 'Prefix Sum', 'Java']