El palíndromo de doble base, como sugiere el nombre, es un número que es palíndromo en 2 bases. Una de las bases es 10 es decir decimal y otra base es k. (que puede ser 2 u otras).
Nota: El número palindrómico, en cualquier base, puede no incluir ceros a la izquierda.
Ejemplo: El número decimal, 585 = 1001001001 2 (binario), es palindrómico en ambas bases.
Un palíndromo es una palabra, frase, número u otra secuencia de caracteres que se lee igual hacia atrás que hacia adelante, como señora o 12321.
Encuentra la suma de todos los números menores que n que son palindrómicos en base 10 y base k.
Ejemplos:
Input : 10 2
Output : 25
Explanation : (here n = 10 and k = 2)
1 3 5 7 9 (they are all palindrome
in base 10 and 2) so sum is :
1 + 3 + 5 + 7 + 9 = 25
Input : 100 2
Output : 157
Explanation : 1 + 3 + 5 + 7 + 9 + 33 + 99 = 157
Método 1: Este método es simple. Para todo número menor que n:
- Comprueba si es un palíndromo en base 10
- En caso afirmativo, conviértalo en base k
- Comprobar si es palíndromo en base k
- En caso afirmativo, agréguelo en total.
Este método es bastante largo ya que verifica cada número, ya sea un palíndromo o no. Entonces, para un número tan grande como 1000000, verifica todos los números.
Si k = 2, entonces un palíndromo en base 2 solo puede ser un número impar, lo que podría reducir las comparaciones a 1000000 / 2 = 500000 (que aún es grande).
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP Program for Checking double base
// Palindrome.
#include <bits/stdc++.h>
using namespace std;
// converts number to base k by changing
// it into string.
string integer_to_string(int n, int base)
{
string str;
while (n > 0) {
int digit = n % base;
n /= base;
str.push_back(digit + '0');
}
return str;
}
// function to check for palindrome
int isPalindrome(int i, int k)
{
int temp = i;
// m stores reverse of a number
int m = 0;
while (temp > 0) {
m = temp % 10 + m * 10;
temp /= 10;
}
// if reverse is equal to number
if (m == i) {
// converting to base k
string str = integer_to_string(m, k);
string str1 = str;
// reversing number in base k
reverse(str.begin(), str.end());
// checking palindrome in base k
if (str == str1) {
return i;
}
}
return 0;
}
// function to find sum of palindromes
void sumPalindrome(int n, int k){
int sum = 0;
for (int i = 1; i < n; i++) {
sum += isPalindrome(i, k);
}
cout << "Total sum is " << sum;
}
// driver function
int main()
{
int n = 100;
int k = 2;
sumPalindrome(n, k);
return 0;
}
Java
// Java Program for Checking double base
// Palindrome.
import java.util.*;
class GFG{
// converts number to base k by changing
// it into string.
static String integer_to_string(int n, int base)
{
String str="";
while (n > 0) {
int digit = n % base;
n /= base;
str+=(char)(digit+'0');
}
return str;
}
// function to check for palindrome
static int isPalindrome(int i, int k)
{
int temp = i;
// m stores reverse of a number
int m = 0;
while (temp > 0) {
m = temp % 10 + m * 10;
temp /= 10;
}
// if reverse is equal to number
if (m == i) {
// converting to base k
String str = integer_to_string(m, k);
StringBuilder sb = new StringBuilder(str);
String str1=sb.reverse().toString();
if (str.equals(str1)) {
return i;
}
}
return 0;
}
// function to find sum of palindromes
static void sumPalindrome(int n, int k){
int sum = 0;
for (int i = 1; i < n; i++) {
sum += isPalindrome(i, k);
}
System.out.println("Total sum is "+sum);
}
// driver function
public static void main(String[] args)
{
int n = 100;
int k = 2;
sumPalindrome(n, k);
}
}
// This code is contributed by mits
Python3
# Python3 Program for Checking
# double base Palindrome.
# converts number to base
# k by changing it into string.
def integer_to_string(n, base):
str = "";
while (n > 0):
digit = n % base;
n = int(n / base);
str = chr(digit + ord('0')) + str;
return str;
# function to check for palindrome
def isPalindrome(i, k):
temp = i;
# m stores reverse of a number
m = 0;
while (temp > 0):
m = (temp % 10) + (m * 10);
temp = int(temp / 10);
# if reverse is equal to number
if (m == i):
# converting to base k
str = integer_to_string(m, k);
str1 = str;
# reversing number in base k
# str=str[::-1];
# checking palindrome
# in base k
if (str[::-1] == str1):
return i;
return 0;
# function to find sum of palindromes
def sumPalindrome(n, k):
sum = 0;
for i in range(n):
sum += isPalindrome(i, k);
print("Total sum is", sum);
# Driver code
n = 100;
k = 2;
sumPalindrome(n, k);
# This code is contributed
# by mits
C#
// C# Program for Checking double base
// Palindrome.
using System;
class GFG{
// converts number to base k by changing
// it into string.
static string integer_to_string(int n, int base1)
{
string str="";
while (n > 0) {
int digit = n % base1;
n /= base1;
str+=(char)(digit+'0');
}
return str;
}
// function to check for palindrome
static int isPalindrome(int i, int k)
{
int temp = i;
// m stores reverse of a number
int m = 0;
while (temp > 0) {
m = temp % 10 + m * 10;
temp /= 10;
}
// if reverse is equal to number
if (m == i) {
// converting to base k
string str = integer_to_string(m, k);
char[] ch = str.ToCharArray();
Array.Reverse(ch);
string str1=new String(ch);;
if (str.Equals(str1)) {
return i;
}
}
return 0;
}
// function to find sum of palindromes
static void sumPalindrome(int n, int k){
int sum = 0;
for (int i = 1; i < n; i++) {
sum += isPalindrome(i, k);
}
Console.WriteLine("Total sum is "+sum);
}
// driver function
static void Main()
{
int n = 100;
int k = 2;
sumPalindrome(n, k);
}
}
// This code is contributed by mits
PHP
<?php
// PHP Program for Checking
// double base Palindrome.
// converts number to base
// k by changing it into string.
function integer_to_string($n, $base)
{
$str = "";
while ($n > 0)
{
$digit = $n % $base;
$n = (int)($n / $base);
$str = ($digit + '0') . $str;
}
return $str;
}
// function to check
// for palindrome
function isPalindrome($i, $k)
{
$temp = $i;
// m stores reverse
// of a number
$m = 0;
while ($temp > 0)
{
$m = ($temp % 10) + ($m * 10);
$temp = (int)($temp / 10);
}
// if reverse is
// equal to number
if ($m == $i)
{
// converting to base k
$str = integer_to_string($m, $k);
$str1 = $str;
// reversing number in base k
// $str=strrev($str);
// checking palindrome
// in base k
if (strcmp(strrev($str), $str1) == 0)
{
return $i;
}
}
return 0;
}
// function to find
// sum of palindromes
function sumPalindrome($n, $k)
{
$sum = 0;
for ($i = 0; $i < $n; $i++)
{
$sum += isPalindrome($i, $k);
}
echo "Total sum is " . $sum;
}
// Driver code
$n = 100;
$k = 2;
sumPalindrome($n, $k);
// This code is contributed
// by mits
?>
Javascript
<script>
// Javascript program for checking
// double base Palindrome.
// Converts number to base k by changing
// it into string.
function integer_to_string(n, base1)
{
let str="";
while (n > 0)
{
let digit = n % base1;
n = parseInt(n / base1, 10);
str += String.fromCharCode(digit +
'0'.charCodeAt());
}
return str;
}
// Function to check for palindrome
function isPalindrome(i, k)
{
let temp = i;
// m stores reverse of a number
let m = 0;
while (temp > 0)
{
m = temp % 10 + m * 10;
temp = parseInt(temp / 10, 10);
}
// If reverse is equal to number
if (m == i)
{
// Converting to base k
let str = integer_to_string(m, k);
let ch = str.split('');
ch.reverse();
let str1 = ch.join("");
if (str == str1)
{
return i;
}
}
return 0;
}
// Function to find sum of palindromes
function sumPalindrome(n, k)
{
let sum = 0;
for(let i = 1; i < n; i++)
{
sum += isPalindrome(i, k);
}
document.write("Total sum is " + sum + "</br>");
}
// Driver code
let n = 100;
let k = 2;
sumPalindrome(n, k);
// This code is contributed by decode2207
</script>
Producción:
Total sum is 157
Método 2: este método es un poco complejo de entender, pero más avanzado que el método 1. En lugar de verificar el palíndromo para dos bases. Este método genera palíndromo en un rango dado.
Supongamos que tenemos un palíndromo de la forma 123321 en base k, entonces los primeros 3 dígitos definen el palíndromo. Sin embargo, los 3 dígitos 123 también definen el palíndromo 12321 . Entonces, el número 123 de 3 dígitos define un palíndromo de 5 dígitos y un palíndromo de 6 dígitos. De donde se sigue que todo número positivo menor que k n genera dos palíndromos menores que k 2n . Esto es válido para cada base k. Ejemplo: digamos k = 10 que es decimal. Entonces para n = 1, todos los números menores que 10 ntiene 2 palíndromos, 1 de longitud par y 1 de longitud impar en 10 2n . Estos son 1, 11 o 2, 22 o 3, 33 y así sucesivamente. Entonces, por 1000000 generamos alrededor de 2000 y por 10 8 generamos alrededor de 20000 palíndromos.
- Comience desde i = 1 y genere un palíndromo impar de él.
- Compruebe si este palíndromo impar generado también es palíndromo en base k
- En caso afirmativo, sume este número a la suma.
- Repita los tres pasos anteriores cambiando i=i+1 hasta que el último palíndromo impar generado haya cruzado el límite.
- Ahora, comience nuevamente desde i = 1 y genere un palíndromo uniforme de él.
- Compruebe si este palíndromo par generado también es palíndromo en base k
- En caso afirmativo, sume este número a la suma.
- Repita los tres pasos anteriores cambiando i=i+1 hasta que el último palíndromo par generado haya cruzado el límite.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP Program for Checking double
// base Palindrome.
#include <bits/stdc++.h>
using namespace std;
// generates even and odd palindromes
int makePalindrome(int n, bool odd)
{
int res = n;
if (odd)
n = n / 10;
while (n > 0) {
res = 10 * res + n % 10;
n /= 10;
}
return res;
}
// Check if a number is palindrome
// in base k
bool isPalindrome(int n, int base)
{
int reversed = 0;
int temp = n;
while (temp > 0) {
reversed = reversed * base +
temp % base;
temp /= base;
}
return reversed == n;
}
// function to print sum of Palindromes
void sumPalindrome(int n, int k){
int sum = 0, i = 1;
int p = makePalindrome(i, true);
// loop for odd generation of
// odd palindromes
while (p < n) {
if (isPalindrome(p, k))
sum += p;
i++;
// cout << p << " ";
p = makePalindrome(i, true);
}
i = 1;
// loop for generation of
// even palindromes
p = makePalindrome(i, false);
while (p < n) {
if (isPalindrome(p, k))
sum += p;
i++;
p = makePalindrome(i, false);
}
// result of all palindromes in
// both bases.
cout << "Total sum is " << sum
<< endl;
}
// driver code
int main()
{
int n = 1000000, k = 2;
sumPalindrome(n ,k);
return 0;
}
Java
// Java Program for Checking double
// base Palindrome.
public class GFG {
// generates even and odd palindromes
static int makePalindrome(int n, boolean odd) {
int res = n;
if (odd) {
n = n / 10;
}
while (n > 0) {
res = 10 * res + n % 10;
n /= 10;
}
return res;
}
// Check if a number is palindrome
// in base k
static boolean isPalindrome(int n, int base) {
int reversed = 0;
int temp = n;
while (temp > 0) {
reversed = reversed * base
+ temp % base;
temp /= base;
}
return reversed == n;
}
// function to print sum of Palindromes
static void sumPalindrome(int n, int k) {
int sum = 0, i = 1;
int p = makePalindrome(i, true);
// loop for odd generation of
// odd palindromes
while (p < n) {
if (isPalindrome(p, k)) {
sum += p;
}
i++;
// cout << p << " ";
p = makePalindrome(i, true);
}
i = 1;
// loop for generation of
// even palindromes
p = makePalindrome(i, false);
while (p < n) {
if (isPalindrome(p, k)) {
sum += p;
}
i++;
p = makePalindrome(i, false);
}
// result of all palindromes in
// both bases.
System.out.println("Total sum is " + sum);
}
// driver code
public static void main(String[] args) {
int n = 1000000, k = 2;
sumPalindrome(n, k);
}
}
Python3
# Python3 Program for Checking double
# base Palindrome.
# Function generates even and
# odd palindromes
def makePalindrome(n, odd):
res = n;
if (odd):
n = int(n / 10);
while (n > 0):
res = 10 * res + n % 10;
n = int(n / 10);
return res;
# Check if a number is palindrome
# in base k
def isPalindrome(n, base):
reversed = 0;
temp = n;
while (temp > 0):
reversed = reversed * base + temp % base;
temp = int(temp / base);
return reversed == n;
# function to print sum of Palindromes
def sumPalindrome(n, k):
sum = 0;
i = 1;
p = makePalindrome(i, True);
# loop for odd generation of
# odd palindromes
while (p < n):
if (isPalindrome(p, k)):
sum += p;
i += 1;
p = makePalindrome(i, True);
i = 1;
# loop for generation of
# even palindromes
p = makePalindrome(i, False);
while (p < n):
if (isPalindrome(p, k)):
sum += p;
i += 1;
p = makePalindrome(i, False);
# result of all palindromes in
# both bases.
print("Total sum is", sum);
# Driver code
n = 1000000;
k = 2;
sumPalindrome(n, k);
# This code is contributed by mits
C#
// C# Program for Checking double
// base1 Palindrome.
public class GFG {
// generates even and odd palindromes
static int makePalindrome(int n, bool odd) {
int res = n;
if (odd) {
n = n / 10;
}
while (n > 0) {
res = 10 * res + n % 10;
n /= 10;
}
return res;
}
// Check if a number is palindrome
// in base1 k
static bool isPalindrome(int n, int base1) {
int reversed = 0;
int temp = n;
while (temp > 0) {
reversed = reversed * base1 + temp % base1;
temp /= base1;
}
return reversed == n;
}
// function to print sum of Palindromes
static void sumPalindrome(int n, int k) {
int sum = 0, i = 1;
int p = makePalindrome(i, true);
// loop for odd generation of
// odd palindromes
while (p < n) {
if (isPalindrome(p, k)) {
sum += p;
}
i++;
p = makePalindrome(i, true);
}
i = 1;
// loop for generation of
// even palindromes
p = makePalindrome(i, false);
while (p < n) {
if (isPalindrome(p, k)) {
sum += p;
}
i++;
p = makePalindrome(i, false);
}
// result of all palindromes in
// both base1s.
System.Console.WriteLine("Total sum is " + sum);
}
// driver code
public static void Main() {
int n = 1000000, k = 2;
sumPalindrome(n, k);
}
}
// This code is contributed by mits
PHP
<?php
// PHP Program for Checking double
// base Palindrome.
// Function generates even and
// odd palindromes
function makePalindrome($n, $odd)
{
$res = $n;
if ($odd)
{
$n = (int)($n / 10);
}
while ($n > 0)
{
$res = 10 * $res + $n % 10;
$n = (int)($n / 10);
}
return $res;
}
// Check if a number is palindrome
// in base k
function isPalindrome($n, $base)
{
$reversed = 0;
$temp = $n;
while ($temp > 0)
{
$reversed = $reversed * $base +
$temp % $base;
$temp = (int)($temp / $base);
}
return $reversed == $n;
}
// function to print sum of Palindromes
function sumPalindrome($n, $k)
{
$sum = 0; $i = 1;
$p = makePalindrome($i, true);
// loop for odd generation of
// odd palindromes
while ($p < $n)
{
if (isPalindrome($p, $k))
{
$sum += $p;
}
$i++;
$p = makePalindrome($i, true);
}
$i = 1;
// loop for generation of
// even palindromes
$p = makePalindrome($i, false);
while ($p < $n)
{
if (isPalindrome($p, $k))
{
$sum += $p;
}
$i++;
$p = makePalindrome($i, false);
}
// result of all palindromes in
// both bases.
echo("Total sum is " . $sum);
}
// Driver code
$n = 1000000; $k = 2;
sumPalindrome($n, $k);
// This code is contributed
// by Mukul Singh.
?>
Javascript
<script>
// javascript Program for Checking var
// base Palindrome.
// generates even and odd palindromes
function makePalindrome(n, odd) {
var res = n;
if (odd) {
n = parseInt(n / 10);
}
while (n > 0) {
res = 10 * res + n % 10;
n = parseInt(n / 10);
}
return res;
}
// Check if a number is palindrome
// in base k
function isPalindrome(n , base) {
var reversed = 0;
var temp = n;
while (temp > 0) {
reversed = reversed * base
+ temp % base;
temp = parseInt(temp/base);
}
return reversed == n;
}
// function to print sum of Palindromes
function sumPalindrome(n , k) {
var sum = 0, i = 1;
var p = makePalindrome(i, true);
// loop for odd generation of
// odd palindromes
while (p < n) {
if (isPalindrome(p, k)) {
sum += p;
}
i++;
// cout << p << " ";
p = makePalindrome(i, true);
}
i = 1;
// loop for generation of
// even palindromes
p = makePalindrome(i, false);
while (p < n) {
if (isPalindrome(p, k)) {
sum += p;
}
i++;
p = makePalindrome(i, false);
}
// result of all palindromes in
// both bases.
document.write("Total sum is " + sum);
}
// driver code
var n = 1000000, k = 2;
sumPalindrome(n, k);
// This code contributed by Princi Singh
</script>
Producción:
Total sum is 872187
Este artículo es una contribución de Shubham Rana . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA