You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
We say a number is sparse if there are no adjacent ones in its binary representation. For example, 21 (10101) is sparse, but 22 (10110) is not. For a given input N, find the smallest sparse number greater than or equal to N.
Do this in faster than O(N log N) time.
*/
#include <bits/stdc++.h>
using namespace std;
// Time : O(logn)
// Space : O(logn)
int findSparseNumber(int n)
{
vector<bool> arr;
while (n != 0)
{
arr.push_back(n & 1);
n >>= 1;
}
arr.push_back(false);
int x = arr.size();
int finalChange = 0;
for (int i = 1; i < x - 1; i++)
{
if (arr[i] == true and arr[i - 1] == true and arr[i + 1] == false)