Roster proof: 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. - Complete
rosterProofProofStripso it returnsclerkCounts. Return it, do not print it.
Example
If readings is [4, 7, 8, 7, 7], then clerkCounts is [0, 0, 0, 0, 0] and rosterProofProofStrip returns [0, 0, 0, 0, 0].
Rules
- If
clerkCountsis empty, return [].
Test data
TEST DATA 1: readings is [20, 0, 20, 12, 2].
TEST DATA 2: readings is [9, 9, 9, 9].
Examples
Input: readings = [20,0,20,12,2] Output: [0,0,0,0,0]
clerkCounts is [0, 0, 0, 0, 0]. rosterProofProofStrip returns that whole list, so return [0, 0, 0, 0, 0].
Input: readings = [9,9,9,9] Output: [0,0,0,0]
clerkCounts is [0, 0, 0, 0]. rosterProofProofStrip returns that whole list, so return [0, 0, 0, 0].
Input: readings = [] Output: []
clerkCounts is []. rosterProofProofStrip returns that whole list, so 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.