C++ এ সুপার প্যালিনড্রোম

ধরুন আমাদের একটি ধনাত্মক পূর্ণসংখ্যা N আছে, যেটিকে বলা হয় সুপারপ্যালিনড্রোম যদি এটি একটি প্যালিনড্রোম হয়, এবং এটি একটি প্যালিনড্রোমের বর্গও। এখন বিবেচনা করুন আমাদের দুটি ধনাত্মক পূর্ণসংখ্যা L এবং R আছে আমাদেরকে [L, R] এর অন্তর্ভুক্ত পরিসরে সুপারপ্যালিন্ড্রোমের সংখ্যা খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুটটি L =5 এবং R =500 এর মত হয়, তাহলে আউটপুট হবে 3, সুপারপ্যালিন্ড্রোমগুলি হল 9, 121, 484৷

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি ফাংশন হেল্পার (), এটি x, m, M, lb, ub,

  লাগবে।

• যদি x> ub হয়, তাহলে −

  • ফেরত

• যদি x>=lb এবং (x * x) প্যালিনড্রোম হয়, তাহলে −

  • (উত্তর 1 দ্বারা বৃদ্ধি করুন)

• আরম্ভ করার জন্য i :=1, যখন m + 2 * i <=M, আপডেট (i 1 দ্বারা বাড়ান), করবেন:

  • W :=10^(m + 2 * i - 1)

  • w :=10^i

  • z শুরু করার জন্য :=1, যখন z <=9, আপডেট করুন (z বাড়ান 1), করুন −

    • সাহায্যকারী(z * W + x * w, m + 2 * i, M, lb, ub)

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

• lb :=L এর বর্গমূল, ub :=R

  এর বর্গমূল

• M :=ub base 10 + 1

  এর লগ সম্পাদন করুন

• z শুরু করার জন্য :=0, যখন z <=9, আপডেট করুন (z বাড়ান 1), do−

  • সাহায্যকারী(z, 1, M, lb, ub)

  • সাহায্যকারী(11 * z, 2, M, lb, ub)

• উত্তর ফেরত দিন

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
class Solution {
   int ans = 0;
   public:
   int superpalindromesInRange(string L, string R){
      long double lb = sqrtl(stol(L)), ub = sqrtl(stol(R));
      int M = log10l(ub) + 1;
      for (int z = 0; z <= 9; z++) {
         helper(z, 1, M, lb, ub);
         helper(11 * z, 2, M, lb, ub);
      }
      return ans;
   }
   private:
   void helper(long x, int m, int M, long double lb, long double ub){
      if (x > ub)
      return;
      if (x >= lb && is_palindrome(x * x))
      ans++;
      for (int i = 1; m + 2 * i <= M; i++) {
         long W = powl(10, m + 2 * i - 1) + 1;
         long w = powl(10, i);
         for (int z = 1; z <= 9; z++)
         helper(z * W + x * w, m + 2 * i, M, lb, ub);
      }
   }
   bool is_palindrome(long x){
      if (x == 0)
      return true;
      if (x % 10 == 0)
      return false;
      long left = x, right = 0;
      while (left >= right) {
         if (left == right || left / 10 == right)
         return true;
         right = 10 * right + (left % 10), left /= 10;
      }
      return false;
   }
};
main(){
   Solution ob;
   cout << (ob.superpalindromesInRange("5", "500"));
}

ইনপুট

"5", "500"

আউটপুট

3