C++ में लगातार 1 के बिना गैर-ऋणात्मक पूर्णांक (Non-negative Integers without Consecutive Ones)

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

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

• एक फंक्शन convert() परिभाषित करें, यह n लेगा,
• ret := खाली स्ट्रिंग
• जब n शून्येतर है, करें -
  • ret := ret + (n mod 2)
  • n := n को दाएं 1 बार शिफ्ट करें
• ret वापस करें
• मुख्य विधि से, निम्न करें -
• bits := convert(num) फंक्शन कॉल करें
• n := bits का आकार
• आकार n का एक ऐरे ones परिभाषित करें, आकार n का एक ऐरे zeroes परिभाषित करें
• ones[0] := 1, zeroes[0] := 1
• i := 1 से प्रारंभ करें, जब i < n, i बढ़ाते हुए, करें -
  • zeroes[i] := zeroes[i - 1] + ones[i - 1]
  • ones[i] := zeroes[i - 1]
• ret := ones[n - 1] + zeroes[n - 1]
• i := n - 2 से प्रारंभ करें, जब i >= 0, i घटाते हुए, करें -
  • यदि bits[i], '0' के समान है और bits[i + 1], '0' के समान है, तो -
    • ret := ret - ones[i]
  • अन्यथा जब bits[i], '1' के समान है और bits[i + 1], '1' के समान है, तो -
    • लूप से बाहर निकलें
• ret वापस करें

बेहतर समझ के लिए निम्न कार्यान्वयन देखें -

उदाहरण

#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