Two Tribes from Taller-Person Counts
Intuit● MediumFULLTIMEOAProblem statement
There are n = a.length distinct people. Person i reports that exactly a[i] people in their own tribe are taller than them. Assign every person to one of two tribes so that all reports can be true.
For this exercise, use the following conventions:
- The tribes are named
AandB. An assignment changes when any particular person moves to the other named tribe. Swapping the two tribes therefore counts as a different assignment. - Either tribe may be empty.
- All heights are distinct, but heights are not supplied and no additional height-order constraints are imposed. A tribe containing
speople is valid exactly when its reported counts contain each integer from0throughs - 1once. - Count only assignments of people to tribes. Do not multiply by possible numeric heights or by ways to interleave the two tribes' height orders.
Return the exact number of valid assignments as a 64-bit integer, without taking a modulus. Return 0 when no assignment satisfies the reports.
Function
countTribeAssignments(a: int[]) → longExamples
Example 1
a = [0,0,1]return = 4Person 2, whose report is 1, must share a tribe with exactly one of persons 0 and 1. There are two choices of that partner and two choices of which named tribe receives the pair, giving 2 × 2 = 4 assignments.
Example 2
a = [0,0,1,1]return = 4Each tribe must contain one person reporting 0 and one reporting 1. Choose the report-0 person for tribe A in two ways and the report-1 person for A in two ways. The other two people join B, giving 4 assignments.
Constraints
- For this exercise, assume
1 <= a.length <= 120. - For this exercise, assume every reported count satisfies
0 <= a[i] < a.length. - Repeated reports are allowed, and the input is not guaranteed to admit a valid assignment.
- The exact answer is at most
2^60, so it fits in a signed 64-bit integer.