সমস্যা বিবরণ
একটি সংখ্যা সুপার প্যালিনড্রোম যদি সেটি প্যালিনড্রোম হয় এবং প্যালিনড্রোম সংখ্যার স্কোয়ারও হয়। Ranges [L, R]-এ কতগুলো সুপার প্যালিনড্রোম আছে তা বের করতে হবে।
উদাহরণ
L = 5, R = 500 → আউটপুট = 3 (সুপার প্যালিনড্রোম: 9, 121, 484)
সমাধান পদ্ধতি
- প্যালিনড্রোম সংখ্যা জেনারেট করে তার স্কোয়ার চেক করা হয়।
- রিকার্সিভ helper() ফাংশন দিয়ে প্যালিনড্রোম বানানো হয় (ওয়েড এবং ইভেন দৈর্ঘ্য)।
- isb_palindrome() দিয়ে স্কোয়ার প্যালিনড্রোম কিনা চেক করা হয়।
- সীমাবদ্ধতা: sqrt(R) পর্যন্ত প্যালিনড্রোম জেনারেট করা হয়।
C++ বাস্তবায়ন
#include <bits/stdc++.h>
using namespace std;
class Solution {
int ans = 0;
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;
}
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);
}
}
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;
}
};
int main() {
Solution ob;
cout << ob.superpalindromesInRange("5", "500");
return 0;
}ইনপুট ও আউটপুট
ইনপুট: "5", "500"
আউটপুট: 3
