Sparse Number Check

Determine whether an integer has no consecutive 1 bits in its binary representation.

bitwise binary conditionals

A non-negative integer is called **sparse** if its binary representation contains no two adjacent 1 bits. For example, 5 (binary `101`) is sparse, while 3 (binary `11`) is not.

Write a function `is_sparse(n: int) -> bool` that returns `True` if `n` is sparse and `False` otherwise.

Constraints

0 ≤ n ≤ 10^9. The input is a Python int. The function should be efficient; an O(number of bits) solution is acceptable.

Example

>>> is_sparse(5)
True
>>> is_sparse(3)
False
>>> is_sparse(0)
True
>>> is_sparse(10)
True

10 points ~15 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

What condition indicates that two adjacent bits are both 1?

Think about the bitwise AND operation between n and n shifted by 1.

If there is any position where both a bit and its neighbor are 1, the result of (n & (n >> 1)) will be non-zero.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.