Interview Questions/Coding/Count Stable Signal Plans

Count Stable Signal Plans

Preview mode. Log in to edit, run, submit, and save progress.

Hard

Count Stable Signal Plans

A manufacturing controller emits a plan made of exactly n signal pulses. Every pulse is one of five modes: R (red), B (blue), G (green), Y (yellow), or V (violet). A plan is stable only when every adjacent pair follows the relay rules below: - R may be followed only by B. - B may be followed by R or G. - G may be followed by R, B, Y, or V. - Y may be followed by G or V. - V may be followed only by R. Return the number of stable signal plans of length n modulo 10^9 + 7.

Examples

Example 1

Input:

n = 1

Output:

Explanation: Any one of R, B, G, Y, and V is a valid one-pulse plan.

Approach hint

Treat each signal mode as a node in a directed graph.

Common mistake

Skipping assumptions, edge cases, or trade-offs can make an otherwise good answer feel incomplete.

solution.cpp