C++-এ অ্যাডিটিভ নাম্বার

শুধু '০' থেকে '৯' পর্যন্ত ডিজিট ধারণকারী একটি স্ট্রিং দেওয়া আছে। এটি অ্যাডিটিভ নাম্বার কিনা তা নির্ধারণ করতে হবে। অ্যাডিটিভ নাম্বার হলো এমন স্ট্রিং যেন ডিজিটগুলো অ্যাডিটিভ সিকোয়েন্স বানাতে পারে। একটি বৈধ অ্যাডিটিভ সিকোয়েন্সে কমপক্ষে তিনটি সংখ্যা থাকতে হবে। প্রথম দুটি সংখ্যা বাদে পরের প্রতিটি সংখ্যা তার আগের দুটি সংখ্যার যোগফল হতে হবে। উদাহরণ: "112358" হলে true, কারণ 2 = 1+1, 3 = 1+2, 5 = 2+3, 8 = 3+5।

সমাধানের ধাপগুলো:

• ok() মেথড বানান যা s, index, prev1, prev2 নেবে:
  • যদি index >= s.size(), true ফেরত দিন।
  • req := prev1 + prev2, num := req স্ট্রিং আকারে।
  • x := খালি স্ট্রিং
  • i = index থেকে s.size()-1 পর্যন্ত:
    • x += s[i]
    • যদি x == num AND ok(s, i+1, prev2, x as integer), true ফেরত দিন।
  • false ফেরত দিন।
• মূল মেথড থেকে:
  • n := num.size()
  • i = 1 থেকে n-2 পর্যন্ত:
    • j = 1 থেকে i পর্যন্ত:
      • s1 := num.substr(0, j)
      • s2 := num.substr(j, i-j+1)
      • x := max(s1.size(), s2.size())
      • যদি x > n-i, পরবর্তী ইটারেশনে যান।
      • যদি (s1[0]=='0' && s1.size()>1) OR (s2[0]=='0' && s2.size()>1), স্কিপ করুন।
      • যদি ok(num, i+1, stol(s1), stol(s2)) true হয়, true ফেরত দিন।
  • false ফেরত দিন।

  উদাহরণ (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