Roster proof: Peak ticket
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. - Find the largest number in
clerkCounts. Store it inlargest. - Complete
rosterProofPeakTicketso it returnslargest. Return it, do not print it.
Example
If readings is [3, 2, 1, 3, 3], then clerkCounts is [0, 0, 0, 0, 0] and rosterProofPeakTicket returns 0.
Rules
- If
clerkCountsis empty, return 0.
Test data
TEST DATA 1: readings is [10, 0, 15, 15, 9].
TEST DATA 2: readings is [2, 8, 8, 8].
Examples
Input: readings = [10,0,15,15,9] Output: 0
clerkCounts is [0, 0, 0, 0, 0]. The largest number is 0. Return 0.
Input: readings = [2,8,8,8] Output: 0
clerkCounts is [0, 0, 0, 0]. The largest number is 0. Return 0.
Input: readings = [] Output: 0
clerkCounts is []. The list is empty, so return 0.
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.