Press parentheses: Boss receipt
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. - Multiply each number in
leastCostsby its position, counting from 1: the first number by 1, the second by 2, and so on. - Add those products. Store the sum in
weightedTotal. - Complete
pressParenthesesBossReceiptso it returnsweightedTotal. Return it, do not print it.
Example
If readings is [2, 9, 7, 2, 7], then leastCosts is [0, 126, 154, 182] and pressParenthesesBossReceipt returns 1442.
Rules
- If
leastCostsis empty, return 0.
Test data
TEST DATA 1: readings is [1, 1, 3, 6, 1].
TEST DATA 2: readings is [10, 10, 2, 10].
Examples
Input: readings = [1,1,3,6,1] Output: 157
leastCosts is [0, 3, 21, 22]. Multiply by positions that start at 1: 1 * (0) + 2 * (3) + 3 * (21) + 4 * (22) = 157. Return 157.
Input: readings = [10,10,2,10] Output: 1600
leastCosts is [0, 200, 400]. Multiply by positions that start at 1: 1 * (0) + 2 * (200) + 3 * (400) = 1600. Return 1600.
Input: readings = [] Output: 0
leastCosts is []. There are no numbers to multiply or add, so 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.