C++ में योजक संख्या

मान लीजिए हमारे पास '0' से '9' तक केवल अंकों वाली एक स्ट्रिंग है, हमें एक फ़ंक्शन लिखना है जो यह निर्धारित करे कि यह एक योजक संख्या है या नहीं। योजक संख्या एक स्ट्रिंग है जिसके अंक योजक अनुक्रम बना सकते हैं। एक वैध योजक अनुक्रम में कम से कम तीन संख्याएं होनी चाहिए। पहले दो संख्याओं को छोड़कर, अनुक्रम में प्रत्येक बाद की संख्या पूर्ववर्ती दो का योग होनी चाहिए।

उदाहरण के लिए, यदि इनपुट "112358" जैसा है, तो उत्तर सही होगा, जैसे 2 = 1 + 1, 3 = 1 + 2, 5 = 2 + 3, 8 = 3 + 5।

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

• ok() नामक एक विधि परिभाषित करें, यह s, index, prev1, prev2 लेगा
• यदि = s का आकार, तो सही लौटाएं
• req := prev1 + prev2 और num := req को स्ट्रिंग के रूप में
• x := एक खाली स्ट्रिंग
• i को index से s के आकार तक लूप करें
  • x := x + s[i]
  • यदि x = num, और ok(s, i + 1, prev2, x को पूर्णांक के रूप में) सही है, तो सही लौटाएं
• गलत लौटाएं
• मुख्य विधि से निम्नलिखित करें:
  • n := num का आकार
  • i को 1 से n - 2 तक लूप करें
    • j को 1 से i तक लूप करें
      • s1 := num का उपस्ट्रिंग 0 से j - 1 तक
      • s2 := num का उपस्ट्रिंग j से i - j तक
      • x := s1 आकार और s2 आकार का अधिकतम
      • यदि x > n - i, तो अगले पुनरावृत्ति के लिए जाएं
      • यदि (s1[0] = 0 और s1 का आकार > 0) OR (s2[0] = 0 और s2 का आकार > 1), तो अगले पुनरावृत्ति पर जाएं
      • यदि ok(num, i + 1, s1 को पूर्णांक और s2 को पूर्णांक) सही है, तो सही लौटाएं
  • गलत लौटाएं

  उदाहरण (C++)

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

  #include <bits/stdc++.h> using namespace std; typedef long long int lli; class Solution {    public:    bool ok(string s, int idx, lli prev1, lli prev2){       if(idx >= s.size()) return true;       lli req = prev1 + prev2;       string num = to_string(req);       string x = "";       for(int i = idx; i < s.size(); i++){          x += s[i];          if(x == num && ok(s, i + 1, prev2, stol(x))) return true;       }       return false;    }    bool isAdditiveNumber(string num) {       int n = num.size();       for(int i = 1; i < n - 1; i++){          for(int j = 1; j <= i; j++){             string s1 = num.substr(0, j);             string s2 = num.substr(j, i - j + 1);             int x = max((int)s1.size(), (int)s2.size());             if(x > n - i) continue;             if((s1[0] == '0' && s1.size() > 1) || (s2[0] == '0' && s2.size() > 1)) continue;             if(ok(num, i + 1, stol(s1), stol(s2))) return true;          }       }       return false;    } }; main(){    Solution ob;    cout << (ob.isAdditiveNumber("112358")); }

  इनपुट

  "112358"

  आउटपुट

  1