Zigzag Binary Pattern
EasyBit Manipulation
Problem
A signal generator is healthy when its output register shows a zigzag pattern: reading the binary form of the positive integer signal (without leading zeros), no two adjacent bits are equal.
Return true if signal has this zigzag pattern, otherwise false.
Example 1
- Input:
- signal = 5
- Output:
- true
101: every neighbour differs.
Example 2
- Input:
- signal = 7
- Output:
- false
111: the bits repeat.
Example 3
- Input:
- signal = 10
- Output:
- true
1010.
Constraints
- 1 ≤ signal < 2^31
Hint
Show the first hint
Compare the number with itself shifted by one position.
Walkthrough
How to approach it
01Clarify before coding
- Do leading zeros count? No, only the bits from the highest set bit down to bit 0.
- Is a single bit a zigzag? Yes, 1 has no adjacent pair to break the rule.
02Brute force
Walk the bits from the bottom, remembering the previous bit, and fail on the first repeat.
Cost: O(log signal) time, O(1) space. Perfectly acceptable; the follow-up is a branch-free O(1) test.
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.