सी++ में योगात्मक संख्या

मान लीजिए कि हमारे पास एक स्ट्रिंग है जिसमें केवल '0' से '9' तक के अंक हैं, हमें यह निर्धारित करने के लिए एक फ़ंक्शन लिखना होगा कि यह एक योगात्मक संख्या है या नहीं। योगात्मक संख्या एक स्ट्रिंग है जिसके अंक योगात्मक अनुक्रम बना सकते हैं। एक मान्य योगात्मक अनुक्रम में कम से कम तीन संख्याएँ होनी चाहिए। यहां पहले दो नंबरों को छोड़कर, अनुक्रम में प्रत्येक बाद की संख्या पिछले दो का योग होना चाहिए। तो अगर इनपुट "112358" जैसा है, तो उत्तर सही होगा, जैसे 2 =1 + 1, 3 =1 + 2, 5 =2 + 3, 8 =3 + 5.

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

ओके () नामक एक विधि को परिभाषित करें, इसमें s, अनुक्रमणिका, prev1, prev2
. लगेगा
यदि अनुक्रमणिका>=s का आकार है, तो सही लौटें
req :=prev1 + prev2 और num :=req as string
x :=एक खाली स्ट्रिंग
s के आकार के सूचकांक की श्रेणी में i के लिए
- x :=x + s[i]
- अगर x =num, और ok(s, i + 1, prev2, x पूर्णांक के रूप में), तो सही लौटें
झूठी वापसी
मुख्य विधि से निम्न कार्य करें -
n :=संख्या का आकार
मैं के लिए 1 से n - 2 की सीमा में
- j के लिए 1 से i तक की श्रेणी में
  - s1 :=0 से j - 1 तक की संख्या का सबस्ट्रिंग
  - s2 :=j से i - j तक अंकों का सबस्ट्रिंग
  - x :=अधिकतम s1 आकार और s2 आकार
  - अगर x> n – i, तो अगले पुनरावृत्ति के लिए जाएं
  - अगर (s1[0] 0 है और s1> 0) का आकार है या (s2[0] 0 है और s2> 1 का आकार है), तो अगले पुनरावृत्ति पर जाएं
  - यदि ठीक है (संख्या, 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"

सी++ में योगात्मक संख्या

उदाहरण(C++)

इनपुट

आउटपुट