Roster proof: Positive proof strip
Inputs
readings is a list of permission masks, one per desk. A mask is a whole number whose binary digits show which clerks are allowed.
Your tasks
- Create a list
clerkCounts. There are n desks and n clerks, both numbered from 0. Here, n is the length ofreadings. Each number inreadingsis a permission mask for one desk. A mask uses binary digits. Each digit is called a bit: a 1 in bit c allows clerk c to use that desk. Bit 0 is the rightmost digit. Assign exactly one clerk to each desk, with no clerk used twice. Follow every permission mask. For each clerk c, count the complete assignments where clerk c gets desk 0. Put those counts in clerk order. A forbidden first choice has count 0. With no desks,clerkCountsis empty. - Create a list
positiveValuesthat keeps only the numbers inclerkCountsthat are greater than 0, in the same order. - Complete
rosterProofPositiveProofStripso it returnspositiveValues. Return it, do not print it.
Example
If readings is [6, 6, 6, 4, 1], then clerkCounts is [0, 0, 0, 0, 0] and rosterProofPositiveProofStrip returns [].
Rules
- Keep repeated numbers.
- If no number is greater than 0, return [].
Test data
TEST DATA 1: readings is [0, 9, 6, 6, 1].
TEST DATA 2: readings is [4, 4, 4, 7].
Examples
Input: readings = [0,9,6,6,1] Output: []
clerkCounts is [0, 0, 0, 0, 0]. Keep only numbers greater than 0, without changing their order. Return [].
Input: readings = [4,4,4,7] Output: []
clerkCounts is [0, 0, 0, 0]. Keep only numbers greater than 0, without changing their order. Return [].
Input: readings = [] Output: []
clerkCounts is []. Keep only numbers greater than 0, without changing their order. Return [].
Input limits
- 0 <= input size <= 6.
- Answers fit in a signed 32-bit integer: -2,147,483,648 through 2,147,483,647.
- There are at most 6 desks. Each permission mask is from 0 to 2 to the power n, minus 1, where n is the number of desks. For n = 3, masks range from 0 to 7.
Efficiency goal
Big-O describes how the work or memory needed grows as the input gets larger.
Efficiency goal: time O(n*n!); extra memory, including the helper list, O(n). n is the input length. These labels describe how work and memory grow with the input.
Practice focus
Build clerkCounts 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.