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 এর জন্য রেঞ্জ ইনডেক্স থেকে s এর সাইজ

  • x :=x + s[i]

  • যদি x =num, এবং ok(s, i + 1, prev2, x পূর্ণসংখ্যা হিসাবে), তাহলে true রিটার্ন করুন

• ফেরত মিথ্যা

• প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -

• n :=সংখ্যার আকার

• 1 থেকে n – 2

  রেঞ্জের জন্য i

  • 1 থেকে i

    পরিসরে j এর জন্য

    • 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"

আউটপুট

1