Cuente todo palíndromo que es cuadrado de un palíndromo

Posted on by Rudeus Greyrat

Dados dos enteros positivos L y R (representados como strings) donde  1\leq L \leq R\leq10^{18} . La tarea es encontrar el número total de superpalíndromos en el rango inclusivo [L, R] . Un palíndromo se llama super-palíndromo si es un palíndromo y también cuadrado de un palíndromo. Ejemplos:

Input: L = "4", R = "1000"
Output: 4
Explanation: 4, 9, 121, and 484 are super-palindromes.

Input : L = "100000", R = "10000000000"
Output : 11

Enfoque: Digamos que  P = R^{2} es un super-palíndromo . Ahora, dado que R es un palíndromo, la primera mitad de los dígitos de R se puede usar para determinar R hasta dos posibilidades. Sea i la primera mitad de los dígitos en R . Por ej. si i = 123 , entonces R = 12321 o R = 123321 . Por lo tanto, podemos iterar a través de todos estos dígitos. Además, cada posibilidad puede tener un número par o impar de dígitos en R . Por lo tanto, iteramos a través de cada i hasta 10 5 y creamos el palíndromo asociado Ry compruebe si R 2 es un palíndromo . También manejaremos los palíndromos pares e impares por separado, y romperemos cada vez que el palíndromo vaya más allá de R . Ahora desde  P \leq 10^{18} , and  R \leq (10^{18})^{\frac{1}{2}} \equiv 10^{9} and  R = i||i^{'} (en Concatenation), donde i ‘ es el reverso de i (en ambos sentidos), entonces nuestro LÍMITE no será mayor que  i\leq10^{5} . A continuación se muestra la implementación del enfoque anterior: 

C++

// C++ implementation of the
// above approach
#include <bits/stdc++.h>
using namespace std;
 
// check if a number is a palindrome
bool ispalindrome(int x)
{
    int ans = 0;
    int temp = x;
    while (temp > 0)
    {
        ans = 10 * ans + temp % 10;
        temp = temp / 10;
    }
    return ans == x;
}
 
// Function to return required count
// of palindromes
int SuperPalindromes(int L, int R)
{
    // Range [L, R]
 
    // Upper limit
    int LIMIT = 100000;
 
    int ans = 0;
 
    // count odd length palindromes
    for (int i = 0 ;i < LIMIT; i++)
    {
        string s = to_string(i); // if s = '1234'
 
        string rs = s.substr(0, s.size() - 1);
        reverse(rs.begin(), rs.end());
 
        // then, t = '1234321'
        string p = s + rs;
        int p_sq     = pow(stoi(p), 2);
        if (p_sq > R)
            break;
        if (p_sq >= L and ispalindrome(p_sq))
            ans = ans + 1;
    }
 
    // count even length palindromes
    for (int i = 0 ;i < LIMIT; i++)
    {
        string s = to_string(i); // if s = '1234'
 
        string rs = s;
        reverse(rs.begin(), rs.end());
        string p = s + rs; // then, t = '12344321'
        int p_sq = pow(stoi(p), 2);
        if (p_sq > R)
            break;
        if (p_sq >= L and ispalindrome(p_sq))
            ans = ans + 1;
    }
 
    // Return count of super-palindromes
    return ans;
}
 
// Driver Code
int main()
{
    string L = "4";
    string R = "1000";
     
    // function call to get required answer
    printf("%d\n", SuperPalindromes(stoi(L),
                                  stoi(R)));
    return 0;
}
 
// This code is contributed
// by Harshit Saini

Java

// Java implementation of the
// above approach
import java.lang.*;
 
class GFG
{
 
// check if a number is a palindrome
public static boolean ispalindrome(int x)
{
    int ans = 0;
    int temp = x;
    while (temp > 0)
    {
        ans = 10 * ans + temp % 10;
        temp = temp / 10;
    }
    return ans == x;
}
 
// Function to return required
// count of palindromes
public static int SuperPalindromes(int L,
                                   int R)
{
    // Range [L, R]
 
    // Upper limit
    int LIMIT = 100000;
 
    int ans = 0;
 
    // count odd length palindromes
    for (int i = 0 ;i < LIMIT; i++)
    {
 
        // if s = '1234'
        String s = Integer.toString(i);
 
        StringBuilder rs = new StringBuilder();
        rs.append(s.substring(0,
                     Math.max(1, s.length() - 1)));
        String srs = rs.reverse().toString();
 
        // then, t = '1234321'
        String p = s + srs;
        int p_sq = (int)(Math.pow(
                         Integer.parseInt(p), 2));
        if (p_sq > R)
        {
            break;
        }
        if (p_sq >= L && ispalindrome(p_sq))
        {
            ans = ans + 1;
        }
    }
 
    // count even length palindromes
    for (int i = 0 ;i < LIMIT; i++)
    {
 
        // if s = '1234'
        String s = Integer.toString(i);
 
        StringBuilder rs = new StringBuilder();
        rs.append(s);
        rs = rs.reverse();
 
        String p = s + rs; // then, t = '12344321'
        int p_sq = (int)(Math.pow(
                         Integer.parseInt(p), 2));
        if (p_sq > R)
        {
            break;
        }
        if (p_sq >= L && ispalindrome(p_sq))
        {
            ans = ans + 1;
        }
    }
 
    // Return count of super-palindromes
    return ans;
}
 
// Driver program
public static void main(String [] args)
{
    String L = "4";
    String R = "1000";
 
    // function call to get required answer
    System.out.println(SuperPalindromes(
       Integer.parseInt(L), Integer.parseInt(R)));
}
}
 
// This code is contributed
// by Harshit Saini

Python3

# Python implementation of the above approach
 
# check if a number is a palindrome
def ispalindrome(x):
    ans, temp = 0, x
    while temp > 0:
        ans = 10 * ans + temp % 10
        temp = temp // 10
    return ans == x
 
# Function to return required count of palindromes
def SuperPalindromes(L, R):
    # Range [L, R]
    L, R = int(L), int(R)
 
    # Upper limit
    LIMIT = 100000
 
    ans = 0
 
    # count odd length palindromes
    for i in range(LIMIT):
        s = str(i)  # if s = '1234'
        p = s + s[-2::-1]  # then, t = '1234321'
        p_sq = int(p) ** 2
        if p_sq > R:
            break
        if p_sq >= L and ispalindrome(p_sq):
            ans = ans + 1
 
    # count even length palindromes
    for i in range(LIMIT):
        s = str(i)  # if s = '1234'
        p = s + s[::-1]  # then, t = '12344321'
        p_sq = int(p) ** 2
        if p_sq > R:
            break
        if p_sq >= L and ispalindrome(p_sq):
            ans = ans + 1
 
    # Return count of super-palindromes
    return ans
 
# Driver program
L = "4"
R = "1000"
 
# function call to get required answer
print(SuperPalindromes(L, R))
 
# This code is written by
# Sanjit_Prasad

C#

// C# implementation of the
// above approach
using System;
 
class GFG
{
 
// check if a number is a palindrome
static bool ispalindrome(int x)
{
    int ans = 0;
    int temp = x;
    while (temp > 0)
    {
        ans = 10 * ans + temp % 10;
        temp = temp / 10;
    }
    return ans == x;
}
 
// utility function used for
// reversing a string
static string Reverse( string s )
{
    char[] charArray = s.ToCharArray();
    Array.Reverse( charArray );
    return new string( charArray );
}
 
// Function to return required
// count of palindromes
static int SuperPalindromes(int L, int R)
{
    // Range [L, R]
 
    // Upper limit
    int LIMIT = 100000;
 
    int ans = 0;
 
    // count odd length palindromes
    for (int i = 0 ;i < LIMIT; i++)
    {
 
        // if s = '1234'
        string s = i.ToString();
 
        string rs = s.Substring(0,
                       Math.Max(1, s.Length - 1));
        rs = Reverse(rs);
 
        // then, t = '1234321'
        string p = s + rs;
        int p_sq = (int)(Math.Pow(
                            Int32.Parse(p), 2));
        if (p_sq > R)
        {
            break;
        }
        if (p_sq >= L && ispalindrome(p_sq))
        {
            ans = ans + 1;
        }
    }
 
    // count even length palindromes
    for (int i = 0 ;i < LIMIT; i++)
    {
 
        // if s = '1234'
        string s = i.ToString();
 
        string rs = Reverse(s);
 
        string p = s + rs; // then, t = '12344321'
        int p_sq = (int)(Math.Pow(
                            Int32.Parse(p), 2));
        if (p_sq > R)
        {
            break;
        }
        if (p_sq >= L && ispalindrome(p_sq))
        {
            ans = ans + 1;
        }
    }
 
    // Return count of super-palindromes
    return ans;
}
 
// Driver Code
public static void Main()
{
    string L = "4";
    String R = "1000";
 
    // function call to get required answer
    Console.WriteLine(SuperPalindromes(
            Int32.Parse(L), Int32.Parse(R)));
}
}
 
// This code is contributed
// by Harshit Saini

PHP

<?php
// PHP implementation of the
// above approach
 
// check if a number is a palindrome
function ispalindrome($x)
{
    $ans = 0;
    $temp = $x;
 
    while($temp > 0)
    {    
        $ans = (10 * $ans) +
               ($temp % 10);
        $temp = (int)($temp / 10);
    }
 
    return $ans == $x;
}
 
// Function to return required
// count of palindromes
function SuperPalindromes($L, $R)
{
    // Range [L, R]
    $L = (int)$L;
    $R = (int)$R;
 
    // Upper limit
    $LIMIT = 100000;
 
    $ans = 0;
 
    // count odd length palindromes
    for($i = 0 ;$i < $LIMIT; $i++)
    {
 
        $s = (string)$i; // if s = '1234'
        $rs = substr($s, 0, strlen($s) - 1);
        $p = $s.strrev($rs); // then, t = '1234321'
        $p_sq = (int)$p ** 2;
        if ($p_sq > $R)
        {
            break;
        }
        if ($p_sq >= $L and ispalindrome($p_sq))
        {
            $ans = $ans + 1;
        }
    }
 
    // count even length palindromes
    for($i = 0 ;$i < $LIMIT; $i++)
    {
        $s = (string)$i; // if s = '1234'
        $p = $s.strrev($s); // then, t = '12344321'
         
        $p_sq = (int)$p ** 2;
 
        if ($p_sq > $R)
        {
            break;
        }
        if ($p_sq >= $L and ispalindrome($p_sq))
        {
            $ans = $ans + 1;
        }
    }
 
    // Return count of super-palindromes
    return $ans;
}
 
 
// Driver Code
$L = "4";
$R = "1000";
 
// function call to get required answer
echo SuperPalindromes($L, $R);
 
// This code is contributed
// by Harshit Saini
?>

Javascript

<script>
 
// JavaScript implementation of the above approach
 
// check if a number is a palindrome
function ispalindrome(x){
    let ans = 0,temp = x
    while(temp > 0){
        ans = 10 * ans + temp % 10
        temp = Math.floor(temp / 10)
    }
    return ans == x
}
 
// Function to return required count of palindromes
function SuperPalindromes(L, R)
{
 
    // Range [L, R]
    L = parseInt(L),R = parseInt(R)
 
    // Upper limit
    let LIMIT = 100000
 
    let ans = 0
 
    // count odd length palindromes
    for(let i = 0; i < LIMIT; i++)
    {
        let s = i.toString() // if s = '1234'
        let rs = s.substring(0,s.length-1)
        rs = rs.split('').reverse().join('')
        let p = s + rs // then, t = '1234321'
        let p_sq = Math.pow(parseInt(p),2)
        if(p_sq > R)
            break
        if(p_sq >= L && ispalindrome(p_sq))
            ans = ans + 1
    }
 
    // count even length palindromes
    for(let i = 0; i < LIMIT; i++)
    {
        let s = i.toString() // if s = '1234'
        let rs = s
        rs = rs.split('').reverse().join('')
        let p = s + rs// then, t = '12344321'
        let p_sq = Math.pow(parseInt(p),2)
        if(p_sq > R)
            break
        if(p_sq >= L && ispalindrome(p_sq))
            ans = ans + 1
    }
 
    // Return count of super-palindromes
    return ans
}
 
// Driver program
let L = "4"
let R = "1000"
 
// function call to get required answer
document.write(SuperPalindromes(L, R))
 
// This code is written by
// shinjanpatra
 
</script>

Producción:

4

Complejidad de tiempo: O(N*log(N)) donde N es el límite superior y el término log(N) proviene de verificar si un candidato es palíndromo.

Publicación traducida automáticamente

Artículo escrito por Sanjit_Prasad y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *