จำนวนเต็มไม่ติดลบที่ไม่มีตัวต่อเนื่องกันใน C++

สมมติว่าเรามีจำนวนเต็มบวก n เราต้องหาจำนวนเต็มที่ไม่เป็นลบที่น้อยกว่าหรือเท่ากับ n ข้อจำกัดคือ การแทนค่าไบนารีจะไม่มีการแทนค่าที่ต่อเนื่องกัน ดังนั้นหากอินพุตคือ 7 คำตอบจะเป็น 5 เนื่องจากการแทนค่าไบนารีของ 5 คือ 101

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน convert() ซึ่งจะใช้เวลา n
• ret :=สตริงว่าง
• ในขณะที่ n ไม่ใช่ศูนย์ ให้ทำ −
  • ret :=ret + (n mod 2)
  • n :=กะขวา n, 1 ครั้ง
• คืนสินค้า
• จากวิธีหลัก ให้ทำดังต่อไปนี้ −
• บิต :=เรียกใช้ฟังก์ชัน convert(num)
• n :=ขนาดของบิต
• กำหนดอาร์เรย์ขนาด n กำหนดศูนย์อาร์เรย์ที่มีขนาด n
• ones[0] :=1, ศูนย์[0] :=1
• สำหรับการเริ่มต้น i :=1 เมื่อฉัน
• ศูนย์[i] :=ศูนย์[i - 1] + ตัว[i - 1]
• ones[i] :=ศูนย์[i - 1]

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

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

อินพุต

7

ผลลัพธ์

5