Non-Negative Integers Without Consecutive Ones in C++

Suppose we have a positive integer n. We have to find the non-negative integers less than or equal to n. The constraint is that the binary representation will not contain consecutive ones. So if the input is 7, then the answer will be 5, as binary representation of 5 is 101.

To solve this, we will follow these steps −

• Define a function convert(), this will take n,
• ret := empty string
• while n is non-zero, do −
  • ret := ret + (n mod 2)
  • n := right shift n, 1 time
• return ret
• From the main method, do the following −
• bits := call the function convert(num)
• n := size of bits
• Define an array ones of size n, Define an array zeroes of size n
• ones[0] := 1, zeroes[0] := 1
• for initialize i := 1, when i < n, update (increase i by 1), do −
  • zeroes[i] := zeroes[i - 1] + ones[i - 1]
  • ones[i] := zeroes[i - 1]
• ret := ones[n - 1] + zeroes[n - 1]
• for initialize i := n - 2, when i >= 0, update (decrease i by 1), do −
  • if bits[i] is same as '0' and bits[i + 1] is same as '0', then −
    • ret := ret - ones[i]
  • otherwise when bits[i] is same as '1' and bits[i + 1] is same as '1', then −
    • Come out from the loop
• return ret

Let us see the following implementation to get better understanding −

Example

 Live Demo

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   string convert(int n){
      string ret = "";
      while(n){
         ret += (n % 2) + '0';
         n >>= 1;
      }
      return ret;
   }
   int findIntegers(int num) {
      string bits = convert(num);
      int n = bits.size();
      vector <int> ones(n);
      vector <int> zeroes(n);
      ones[0] = zeroes[0] = 1;
      for(int i = 1; i < n; i++){
         zeroes[i] = zeroes[i - 1] + ones[i - 1];
         ones[i] = zeroes[i - 1];
      }
      int ret = ones[n - 1] + zeroes[n - 1];
      for(int i = n - 2; i >= 0; i--){
         if(bits[i] == '0' && bits[i + 1] == '0') ret -= ones[i];
         else if(bits[i] == '1' && bits[i + 1]== '1') break;
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.findIntegers(7));
}

Input

7

Output

5