A fungal network is a binary tree; each node has an integer strain value. A uniform colony is a subtree (a node together with all of its descendants) in which every node has the same strain value. A single leaf is always a uniform colony.
Report the number of uniform colonies in the network.
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 strain or null for a missing child. Children of null nodes are omitted.
A single integer: the number of uniform colonies.
Example 1
Input
3 1 1 1
Expected
3
Explanation
Both leaves are uniform colonies, and the whole tree is all 1's, so it is uniform too. That is 3 uniform colonies.
Example 2
Input
3 2 2 3
Expected
2
Explanation
Each leaf (the 2 and the 3) is a uniform colony, but the whole tree contains both 2 and 3, so it is not uniform. The answer is 2.
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 →