Adjacent flag configurations

Write codeMedium12 min

Your task

A rollout tool stores n feature flags as a row of bits, one per flag, each on (1) or off (0). To limit blast radius, policy forbids enabling two adjacent flags at the same time. Return how many distinct flag configurations of length n satisfy the policy. For n = 0 return 1 (the empty configuration). For example, n = 2 allows 00, 01, and 10, but not 11, so the answer is 3.

Examples

count_valid_flag_masks(n: int) -> int
Example 1
Inputcount_valid_flag_masks(2)
Output3
Example 2
Inputcount_valid_flag_masks(3)
Output5