मान लीजिए हमारे पास एक धनात्मक पूर्णांक N है, जिसे सुपरपैलिंड्रोम कहा जाता है यदि यह एक पैलिंड्रोम है, और यह एक पैलिंड्रोम का वर्ग भी है। अब हमारे पास दो धनात्मक पूर्णांक L और R हैं, हमें [L, R] की समावेशी रेंज में सुपरपैलिंड्रोम की संख्या ढूंढनी है।
उदाहरण के लिए, यदि L = 5 और R = 500, तो आउटपुट 3 होगा, सुपरपैलिंड्रोम हैं 9, 121, 484।
हल करने का दृष्टिकोण
हम सभी पैलिंड्रोम रूट उत्पन्न करते हैं जिनके वर्ग रेंज में आते हैं:
lb = sqrt(L), ub = sqrt(R) की गणना करें
सभी पैलिंड्रोम संख्याओं को 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;
}
};
int main(){
Solution ob;
cout << (ob.superpalindromesInRange("5", "500"));
return 0;
}
इनपुट
"5", "500"
आउटपुट
3
