A museum's rooms form a binary tree. A camera installed in a room monitors that room, its parent room, and its direct child rooms. Determine the minimum number of cameras needed so that every room is monitored by at least one camera.
Line 1: an integer k, the number of tokens on line 2.
Line 2: k space-separated tokens giving the tree in level order. The first token is the root; each subsequent token is an integer room id or null for a missing child. Children of null nodes are omitted. (Ids do not affect the answer.)
A single integer: the minimum number of cameras.
Example 1
Input
5 0 0 null 0 0
Expected
1
Explanation
One camera placed at the root's only child monitors the root, that child, and its two children, covering all four rooms. One camera suffices.
Example 2
Input
9 0 null 0 null 0 null 0 null 0
Expected
2
Explanation
This is a chain of five rooms. Placing cameras on the second and fourth rooms monitors all five, and no single camera can. Two cameras are needed.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →