FLTRCK - Editorial

PROBLEM LINK:

Practice

Contest

Author: samhenry97
Editorialist: samhenry97

DIFFICULTY:

Easy

PREREQUISITES:

Array Sum, Binary Search

PROBLEM:

What is the largest amount of items of an array that sums to a number <= a given value?

QUICK EXPLANATION:

We can construct a sum array, and then use binary searches for each query.

EXPLANATION:

First, we read the integers and sort them. Then, we create an array sum, which is a cache of the sums of each subarray 0…i.

Now, for each query, we can run a binary search to see where the largest sum is that fits the weight.

AUTHOR’S AND TESTER’S SOLUTIONS: