Số nguyên không âm mà không có số liên tiếp trong C ++

Giả sử chúng ta có một số nguyên dương n. Chúng ta phải tìm các số nguyên không âm nhỏ hơn hoặc bằng n. Hạn chế là biểu diễn nhị phân sẽ không chứa những cái liên tiếp. Vì vậy, nếu đầu vào là 7, thì câu trả lời sẽ là 5, vì biểu diễn nhị phân của 5 là 101.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một hàm convert (), điều này sẽ mất n,
• ret:=chuỗi trống
• while n khác 0, do -
  • ret:=ret + (n mod 2)
  • n:=ca phải n, 1 lần
• trả lời lại
• Từ phương pháp chính, hãy thực hiện như sau -
• bits:=gọi hàm convert (num)
• n:=kích thước của bit
• Xác định một mảng có kích thước n, Xác định một mảng có kích thước n
• cái [0]:=1, không [0]:=1
• để khởi tạo i:=1, khi i
• zeroes [i]:=zeroes [i - 1] + những cái [i - 1]
• những cái [i]:=0es [i - 1]

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

7

Đầu ra

5