Super Palindromes ใน C ++

สมมติว่าเรามีจำนวนเต็มบวก N ซึ่งเรียกว่า superpalindrome หากเป็นพาลินโดรม และมันคือกำลังสองของพาลินโดรมด้วย ตอนนี้ให้พิจารณาว่าเรามีจำนวนเต็มบวกสองจำนวน L และ R เราต้องหาจำนวนของ superpalindromes ในช่วง [L, R] ที่รวมไว้

ดังนั้น หากอินพุตมีค่าเท่ากับ L =5 และ R =500 เอาต์พุตจะเป็น 3 ดังนั้น superpalindromes จะเป็น 9, 121, 484

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนด function helper() ซึ่งจะใช้เวลา 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 ฐาน 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