FastPrep
Problem · Dynamic Programming

Math Homework

Learn this problem
● MediumSuperhuman logoSuperhumanFULLTIMENEW GRADOA

Problem statement

You are given a sorted array points representing the point values of homework problems in the order they appear.

A student must solve the first problem at index 0. After solving a problem at index i, the student may solve either the next problem i + 1 or skip one problem and solve i + 2.

The student continues until the difference between the maximum and minimum point values among the solved problems is at least threshold. If that can never be achieved, the student must solve all problems.

Return the minimum number of problems the student needs to solve.

Function

minProblemsToSolve(points: int[], threshold: int) → int

Complete the function minProblemsToSolve in the editor below.

minProblemsToSolve has the following parameters:

  • int[] points: sorted point values for the homework problems
  • int threshold: the required spread between the minimum and maximum solved point values

Returns

int: the minimum number of problems that must be solved

Examples

Example 1

points = [1, 2, 3, 5, 8]threshold = 4return = 3
Solve the problems worth 1, 3, and 8. The solved values have spread 8 - 1 = 7, and it takes only 3 problems.

Example 2

points = [1, 2, 3, 4, 5]threshold = 4return = 3
Solve the problems worth 1, 3, and 5. The spread is exactly 4, so the answer is 3.

Example 3

points = [4, 5, 6, 7]threshold = 10return = 4
Even after solving every problem, the spread is only 7 - 4 = 3, so the student must solve all 4 problems.

Constraints

  • points is sorted in non-decreasing order.
  • 1 ≤ points[i] < 1000.
  • 1 ≤ threshold < 1000.

More Superhuman problems

drafts saved locally
public int minProblemsToSolve(int[] points, int threshold) {
  // write your code here
}
points[1, 2, 3, 5, 8]
threshold4
expected3
checking account