Find Next Sparse Number - GeeksforGeeks

Find Next Sparse Number - GeeksforGeeks

Find Next Sparse Number

A number is Sparse if there are no two adjacent 1s in its binary representation. For example 5 (binary representation: 101) is sparse, but 6 (binary representation: 110) is not sparse.
Given a number x, find the smallest Sparse number which greater than or equal to x.

Examples:

Input: x = 6  Output: Next Sparse Number is 8    Input: x = 4  Output: Next Sparse Number is 4    Input: x = 38  Output: Next Sparse Number is 40    Input: x = 44  Output: Next Sparse Number is 64  

We strongly recommend you to minimize your browser and try this yourself first.

A Simple Solution is to do following:

1) Write a utility function isSparse(x) that takes a number      and returns true if x is sparse, else false.  This function     can be easily written by traversing the bits of input number.  2) Start from x and do following      while(1)     {        if (isSparse(x))           return x;        else            x++     }  

Time complexity of isSparse() is O(Log x). Time complexity of this solution is O(x Log x). The next sparse number can be at most O(x) distance away.

Read full article from Find Next Sparse Number - GeeksforGeeks