सी ++ में लगातार वाले के बिना गैर-नकारात्मक पूर्णांक

मान लीजिए कि हमारे पास एक धनात्मक पूर्णांक n है। हमें n से कम या उसके बराबर गैर-ऋणात्मक पूर्णांक ज्ञात करने हैं। बाधा यह है कि द्विआधारी प्रतिनिधित्व में लगातार वाले नहीं होंगे। तो अगर इनपुट 7 है, तो उत्तर 5 होगा, क्योंकि 5 का बाइनरी प्रतिनिधित्व 101 है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एक फ़ंक्शन कन्वर्ट को परिभाषित करें (), इसमें n लगेगा,
• रिट:=खाली स्ट्रिंग
• जबकि n गैर-शून्य है, करें −
  • ret :=ret + (n mod 2)
  • n :=दायां शिफ्ट n, 1 बार
• रिटर्न रिटर्न
• मुख्य विधि से, निम्न कार्य करें -
• बिट्स:=फंक्शन कन्वर्ट को कॉल करें (संख्या)
• n :=बिट्स का आकार
• आकार n के सरणी को परिभाषित करें, n आकार के सरणी शून्य को परिभाषित करें
• वाले[0] :=1, शून्य[0] :=1
• इनिशियलाइज़ i :=1 के लिए, जब i करें
• शून्य[i] :=शून्य[i - 1] + वाले[i - 1]
• वाले[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