Suma de Números K-espejo
Un número k-espejo es un entero positivo sin ceros a la izquierda que se lee igual tanto hacia adelante como hacia atrás en base-10 así como en base-k.
- Por ejemplo,
9es un número 2-espejo. La representación de9en base-10 y base-2 son9y1001respectivamente, las cuales se leen igual tanto hacia adelante como hacia atrás. - Por el contrario,
4no es un número 2-espejo. La representación de4en base-2 es100, la cual no se lee igual hacia adelante y hacia atrás.
Dada la base k y el número n, devuelve la suma de los n números k-espejo más pequeños.
Ejemplos
Ejemplo 1:
Input: k = 2, n = 5 Output: 25 Explicación: Los 5 números 2-espejo más pequeños y sus representaciones en base-2 se listan a continuación: base-10 base-2 1 1 3 11 5 101 7 111 9 1001 Su suma = 1 + 3 + 5 + 7 + 9 = 25.Ejemplo 2:
Input: k = 3, n = 7 Output: 499 Explicación: Los 7 números 3-espejo más pequeños y sus representaciones en base-3 se listan a continuación: base-10 base-3 1 1 2 2 4 11 8 22 121 11111 151 12121 212 21212 Su suma = 1 + 2 + 4 + 8 + 121 + 151 + 212 = 499.Ejemplo 3:
Input: k = 7, n = 17 Output: 20379000 Explicación: Los 17 números 7-espejo más pequeños son: 1, 2, 3, 4, 5, 6, 8, 121, 171, 242, 292, 16561, 65656, 2137312, 4602064, 6597956, 6958596Soluciones
Python
class Solution:
def is_palindrome(self, s):
"""Verifica si una cadena es un palíndromo."""
return s == s[::-1]
def convert_to_base_k(self, num, k):
"""Convierte un número a base k y retorna como string."""
if num == 0:
return "0"
digits = []
while num > 0:
digits.append(str(num % k))
num //= k
return ''.join(digits)
def generate_palindrome(self, half, is_odd_length):
"""Genera un palíndromo a partir de la primera mitad."""
if is_odd_length:
return half + half[-2::-1] # Excluye el dígito del medio
else:
return half + half[::-1]
def kMirror(self, k: int, n: int) -> int:
"""Encuentra la suma de los primeros n números k-mirror."""
total_sum = 0
found_count = 0
length = 1
while found_count < n:
# Calcular límites para la primera mitad del palíndromo
half_length = (length + 1) // 2
start = 10 ** (half_length - 1)
end = 10 ** half_length
# Generar todos los palíndromos de longitud 'length'
for half_num in range(start, end):
half_str = str(half_num)
is_odd = length % 2 == 1
# Generar el palíndromo completo
palindrome_str = self.generate_palindrome(half_str, is_odd)
palindrome_num = int(palindrome_str)
# Convertir a base k y verificar si también es palíndromo
base_k_str = self.convert_to_base_k(palindrome_num, k)
if self.is_palindrome(base_k_str):
total_sum += palindrome_num
found_count += 1
if found_count == n:
return total_sum
length += 1
return total_sum