FastPrep
Problem · Heap

Women in STEM Charity

Learn this problem
● MediumCanva logoCanvaOA

Problem statement

Stacey is coordinating a beach clean-up event with her university's Women in STEM charity branch. The beach is covered with tin cans of varying weights arranged in a single line, indexed from 0 to n-1.

Stacey uses a scooper that can pick up three adjacent cans at a time. For each selection:

  • She identifies the lightest remaining can with weight w
  • She uses the scooper to pick up that can along with its two adjacent cans (or fewer if at the edge)
  • She continues this process until there are no cans left on the beach

    • If multiple cans have the lightest weight, Stacey selects the one with the smallest index. If a can has fewer than two adjacent cans, she removes the available adjacent cans.

    Determine the sum of the weights of the lightest cans she picks in each selection.

    Function

    findTotalWeight(cans: int[]) → int

    Complete the function findTotalWeight in the editor with the following parameters:

    • int cans[]: the weights of the cans on the beach

    Returns

    int: the sum of the minimum-weight cans at each selection

    Constraints

    • 3 ≤ length of cans ≤ 2000
    • 1 ≤ cans[i] ≤ 10^5

    Examples

    Example 1

    cans = [5, 4, 1, 3, 2]return = 3
    Let there be n = 5 cans on the beach with weights represented by cans = [5, 4, 1, 3, 2].
  • First, choose the minimum weight, i.e., 1, and add that weight to the total. The cans with weights 4, 1, and 3 are removed. The array of cans is now [5, 2].
  • Then, choose the minimum weight, i.e., 2, and add that weight to the total. The cans with weights 2 and 5 are removed, and there are no more cans on the beach.
    • Hence, the total is 1 + 2 = 3.

    More Canva problems

    drafts saved locally
    public int findTotalWeight(int[] cans) {
  // write your code here
}
    cans[5, 4, 1, 3, 2]
    expected3
    checking account