Press parentheses: Even-key census
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. - Count the even numbers in
leastCosts. Store the count inevenCount. A number is even when it divides by 2 with no remainder. - Complete
pressParenthesesEvenKeyCensusso it returnsevenCount. Return it, do not print it.
Example
If readings is [9, 7, 10, 6, 7], then leastCosts is [0, 630, 798, 1155] and pressParenthesesEvenKeyCensus returns 3.
Rules
- 0 counts as an even number.
- If
leastCostsis empty, return 0.
Test data
TEST DATA 1: readings is [7, 1, 2, 1, 2].
TEST DATA 2: readings is [9, 6, 6, 6].
Examples
Input: readings = [7,1,2,1,2] Output: 3
leastCosts is [0, 14, 9, 18]. The even numbers are [0, 14, 18]. There are 3, so return 3.
Input: readings = [9,6,6,6] Output: 3
leastCosts is [0, 324, 540]. The even numbers are [0, 324, 540]. There are 3, so return 3.
Input: readings = [] Output: 0
leastCosts is []. The even numbers are []. There are 0, 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.