Signal Patterns Without Double Pulses
EasyBacktracking
Problem
A sensor emits a pattern of n time slots, each either 0 (quiet) or 1 (pulse). Two pulses in consecutive slots would overheat it.
Return every pattern of length n that never has two 1s next to each other, as strings, in any order.
Example 1
- Input:
- n = 3
- Output:
- ["000", "001", "010", "100", "101"]
"011", "110" and "111" contain two adjacent pulses and are excluded.
Example 2
- Input:
- n = 1
- Output:
- ["0", "1"]
Constraints
- 1 ≤ n ≤ 18
Hint
Show the first hint
Build the pattern left to right, one slot at a time.
Walkthrough
How to approach it
01Clarify before coding
- Is a single pulse allowed at either end? Yes, only adjacent pairs are forbidden.
- Return strings or lists? Strings of '0' and '1', in any order.
- How big can n be? 18, so 2^18 raw strings would be 262,144, but far fewer are valid.
02Brute force
Generate all 2^n strings and filter out those containing "11".
Cost: O(n · 2^n). Valid patterns grow like Fibonacci (about 1.618^n), so for n = 18 you build 262,144 strings to keep 6,765.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.