Press parentheses: Positive-ink invoice
Inputs
readings is a list of positive whole numbers that describe matrix sizes.
Your tasks
- Create a list
leastCosts.readingslists matrix sizes. A matrix is a table of numbers with rows and columns. Matrix 0 hasreadings[0]rows andreadings[1]columns. Matrix 1 hasreadings[1]rows andreadings[2]columns, and so on. Multiplying an a-by-b matrix by a b-by-c matrix costs a * b * c number multiplications. You may group the matrices with brackets, but must keep their order. Different groups can have different costs. For the first matrix alone, record 0. Then record the least total cost for the first two matrices, the first three, and so on. Fewer than two size numbers means there are no matrices, soleastCostsis empty. - Add only the numbers in
leastCoststhat are greater than 0. Store the sum inpositiveTotal. - Complete
pressParenthesesPositiveInkInvoiceso it returnspositiveTotal. Return it, do not print it.
Example
If readings is [5, 6, 7, 6, 7], then leastCosts is [0, 210, 420, 630] and pressParenthesesPositiveInkInvoice returns 1260.
Rules
- Skip zeros.
- If no number is greater than 0, return 0.
Test data
TEST DATA 1: readings is [4, 1, 1, 10, 10].
TEST DATA 2: readings is [5, 5, 5, 3].
Examples
Input: readings = [4,1,1,10,10] Output: 192
leastCosts is [0, 4, 44, 144]. Keep [4, 44, 144] and add those numbers. Return 192.
Input: readings = [5,5,5,3] Output: 275
leastCosts is [0, 125, 150]. Keep [125, 150] and add those numbers. Return 275.
Input: readings = [] Output: 0
leastCosts is []. Keep [] and add those numbers. Return 0.
Input limits
- 0 <= input size <= 16.
- Answers fit in a signed 32-bit integer: -2,147,483,648 through 2,147,483,647.
- Every dimension is an integer from 1 through 10; there are at most 16 dimensions.
Efficiency goal
Big-O describes how the work or memory needed grows as the input gets larger.
Efficiency goal: time O(n^3); extra memory, including the helper list, O(n^2). n is the input length. These labels describe how work and memory grow with the input.
Practice focus
Build leastCosts first, then return exactly what the tasks ask for. Follow the order, keep repeated values when the rule says so, and check the empty case.