Dado N (muy grande), la tarea es imprimir el número palindrómico más grande obtenido al permutar los dígitos de N. Si no es posible hacer un número palindrómico, imprima un mensaje apropiado.
Ejemplos:
Input : 313551 Output : 531135 Explanations : 531135 is the largest number which is a palindrome, 135531, 315513 and other numbers can also be formed but we need the highest of all of the palindromes. Input : 331 Output : 313 Input : 3444 Output : Palindrome cannot be formed
Enfoque ingenuo: el enfoque ingenuo será probar todas las permutaciones posibles e imprimir la mayor de tales combinaciones, que es un palíndromo.
Enfoque eficiente: un enfoque eficiente será utilizar el algoritmo Greedy. Dado que el número es grande, almacene el número en una string. Almacene el recuento de ocurrencias de cada dígito en el número dado en un mapa. Comprueba si es posible formar un palíndromo o no. Si los dígitos del número dado se pueden reorganizar para formar un palíndromo, aplique el enfoque codicioso para obtener el número. Verifique la aparición de cada dígito (9 a 0) y coloque todos los dígitos disponibles en la parte delantera y trasera. Inicialmente, el puntero frontal estará en el índice 0, ya que el dígito más grande se colocará primero para que el número sea más grande. Con cada paso, mueva el indicador delantero 1 posición hacia adelante. Si el dígito aparece un número impar de veces, entonces coloqueun dígito en el medio y el resto del número par de dígitos al frente y atrás . Siga repitiendo el proceso (mapa[dígito]/2) la cantidad de veces para un solo dígito. Después de colocar un dígito en particular que aparece un número par de veces al frente y al reverso, mueva el puntero frontal un paso hacia adelante. La colocación se realiza hasta que map[digit] es 0. La array de caracteres tendrá el número palindrómico más grande posible después de completar la colocación de dígitos con avidez.
En el peor de los casos, la complejidad del tiempo será O(10 * (longitud de string/2)) , en caso de que el número consista en el mismo dígito en cada posición.
A continuación se muestra la implementación de la idea anterior:
C++
// CPP program to print the largest palindromic
// number by permuting digits of a number
#include <bits/stdc++.h>
using namespace std;
// function to check if a number can be
// permuted to form a palindrome number
bool possibility(unordered_map<int, int> m,
int length, string s)
{
// counts the occurrence of number which is odd
int countodd = 0;
for (int i = 0; i < length; i++) {
// if occurrence is odd
if (m[s[i] - '0'] & 1)
countodd++;
// if number exceeds 1
if (countodd > 1)
return false;
}
return true;
}
// function to print the largest palindromic number
// by permuting digits of a number
void largestPalindrome(string s)
{
// string length
int l = s.length();
// map that marks the occurrence of a number
unordered_map<int, int> m;
for (int i = 0; i < l; i++)
m[s[i] - '0']++;
// check the possibility of a palindromic number
if (possibility(m, l, s) == false) {
cout << "Palindrome cannot be formed";
return;
}
// string array that stores the largest
// permuted palindromic number
char largest[l];
// pointer of front
int front = 0;
// greedily start from 9 to 0 and place the
// greater number in front and odd in the
// middle
for (int i = 9; i >= 0; i--) {
// if the occurrence of number is odd
if (m[i] & 1) {
// place one odd occurring number
// in the middle
largest[l / 2] = char(i + 48);
// decrease the count
m[i]--;
// place the rest of numbers greedily
while (m[i] > 0) {
largest[front] = char(i + 48);
largest[l - front - 1] = char(i + 48);
m[i] -= 2;
front++;
}
}
else {
// if all numbers occur even times,
// then place greedily
while (m[i] > 0) {
// place greedily at front
largest[front] = char(i + 48);
largest[l - front - 1] = char(i + 48);
// 2 numbers are placed, so decrease the count
m[i] -= 2;
// increase placing position
front++;
}
}
}
// print the largest string thus formed
for (int i = 0; i < l; i++)
cout << largest[i];
}
// Driver Code
int main()
{
string s = "313551";
largestPalindrome(s);
return 0;
}
Java
// JAVA program to print the
// largest palindromic number
// by permuting digits of a number
import java.util.*;
class GFG{
// Function to check if a number can be
// permuted to form a palindrome number
static boolean possibility(HashMap<Integer,
Integer> m,
int length, String s)
{
// counts the occurrence of number
// which is odd
int countodd = 0;
for (int i = 0; i < length; i++)
{
// if occurrence is odd
if (m.get(s.charAt(i) - '0') % 2 == 1)
countodd++;
// if number exceeds 1
if (countodd > 1)
return false;
}
return true;
}
// function to print the largest
// palindromic number by permuting
// digits of a number
static void largestPalindrome(String s)
{
// String length
int l = s.length();
// map that marks the occurrence
// of a number
HashMap<Integer,
Integer> m = new HashMap<>();
for (int i = 0; i < l; i++)
if(m.containsKey(s.charAt(i) - '0'))
m.put(s.charAt(i) - '0',
m.get(s.charAt(i) - '0') + 1);
else
m.put(s.charAt(i) - '0', 1);
// check the possibility of a
// palindromic number
if (possibility(m, l, s) == false)
{
System.out.print("Palindrome cannot be formed");
return;
}
// String array that stores
// the largest permuted
// palindromic number
char []largest = new char[l];
// pointer of front
int front = 0;
// greedily start from 9 to 0
// and place the greater number
// in front and odd in the middle
for (int i = 9; i >= 0; i--)
{
// if the occurrence of
// number is odd
if (m.containsKey(i) &&
m.get(i)%2==1)
{
// place one odd occurring
// number in the middle
largest[l / 2] = (char)(i + 48);
// decrease the count
m.put(i, m.get(i)-1);
// place the rest of
// numbers greedily
while (m.get(i) > 0)
{
largest[front] = (char)(i + 48);
largest[l - front - 1] =
(char)(i + 48);
m.put(i, m.get(i) - 2);
front++;
}
}
else
{
// if all numbers occur even
// times, then place greedily
while (m.containsKey(i) &&
m.get(i) > 0)
{
// place greedily at front
largest[front] = (char)(i + 48);
largest[l - front - 1] =
(char)(i + 48);
// 2 numbers are placed,
// so decrease the count
m.put(i, m.get(i) - 2);
// increase placing position
front++;
}
}
}
// print the largest String
// thus formed
for (int i = 0; i < l; i++)
System.out.print(largest[i]);
}
// Driver Code
public static void main(String[] args)
{
String s = "313551";
largestPalindrome(s);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program to print the largest palindromic
# number by permuting digits of a number
from collections import defaultdict
# Function to check if a number can be
# permuted to form a palindrome number
def possibility(m, length, s):
# counts the occurrence of
# number which is odd
countodd = 0
for i in range(0, length):
# if occurrence is odd
if m[int(s[i])] & 1:
countodd += 1
# if number exceeds 1
if countodd > 1:
return False
return True
# Function to print the largest palindromic
# number by permuting digits of a number
def largestPalindrome(s):
# string length
l = len(s)
# map that marks the occurrence of a number
m = defaultdict(lambda:0)
for i in range(0, l):
m[int(s[i])] += 1
# check the possibility of a
# palindromic number
if possibility(m, l, s) == False:
print("Palindrome cannot be formed")
return
# string array that stores the largest
# permuted palindromic number
largest = [None] * l
# pointer of front
front = 0
# greedily start from 9 to 0 and place the
# greater number in front and odd in the middle
for i in range(9, -1, -1):
# if the occurrence of number is odd
if m[i] & 1:
# place one odd occurring number
# in the middle
largest[l // 2] = chr(i + 48)
# decrease the count
m[i] -= 1
# place the rest of numbers greedily
while m[i] > 0:
largest[front] = chr(i + 48)
largest[l - front - 1] = chr(i + 48)
m[i] -= 2
front += 1
else:
# if all numbers occur even times,
# then place greedily
while m[i] > 0:
# place greedily at front
largest[front] = chr(i + 48)
largest[l - front - 1] = chr(i + 48)
# 2 numbers are placed,
# so decrease the count
m[i] -= 2
# increase placing position
front += 1
# print the largest string thus formed
for i in range(0, l):
print(largest[i], end = "")
# Driver Code
if __name__ == "__main__":
s = "313551"
largestPalindrome(s)
# This code is contributed by Rituraj Jain
C#
// C# program to print the largest
// palindromic number by permuting
// digits of a number
using System;
using System.Collections.Generic;
class GFG{
// Function to check if a number can be
// permuted to form a palindrome number
static bool possibility(Dictionary<int, int> m,
int length, string s)
{
// Counts the occurrence of number
// which is odd
int countodd = 0;
for(int i = 0; i < length; i++)
{
// If occurrence is odd
if ((m[s[i] - '0'] & 1) != 0)
countodd++;
// If number exceeds 1
if (countodd > 1)
return false;
}
return true;
}
// Function to print the largest palindromic
// number by permuting digits of a number
static void largestPalindrome(string s)
{
// string length
int l = s.Length;
// Map that marks the occurrence of a number
Dictionary<int,
int> m = new Dictionary<int,
int>();
for(int i = 0; i < 10; i++)
m[i] = 0;
for(int i = 0; i < l; i++)
m[s[i] - '0']++;
// Check the possibility of a
// palindromic number
if (possibility(m, l, s) == false)
{
Console.Write("Palindrome cannot be formed");
return;
}
// string array that stores the largest
// permuted palindromic number
char []largest = new char[l];
// Pointer of front
int front = 0;
// Greedily start from 9 to 0 and place the
// greater number in front and odd in the
// middle
for(int i = 9; i >= 0; i--)
{
// If the occurrence of number is odd
if ((m[i] & 1) != 0)
{
// Place one odd occurring number
// in the middle
largest[l / 2] = (char)(i + '0');
// Decrease the count
m[i]--;
// Place the rest of numbers greedily
while (m[i] > 0)
{
largest[front] = (char)(i + '0');
largest[l - front - 1] = (char)(i + '0');
m[i] -= 2;
front++;
}
}
else
{
// If all numbers occur even times,
// then place greedily
while (m[i] > 0)
{
// Place greedily at front
largest[front] = (char)(i + '0');
largest[l - front - 1] = (char)(i + '0');
// 2 numbers are placed, so
// decrease the count
m[i] -= 2;
// Increase placing position
front++;
}
}
}
// Print the largest string thus formed
for(int i = 0; i < l; i++)
{
Console.Write(largest[i]);
}
}
// Driver Code
public static void Main(string[] args)
{
string s = "313551";
largestPalindrome(s);
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// Javascript program to print the largest palindromic
// number by permuting digits of a number
// function to check if a number can be
// permuted to form a palindrome number
function possibility(m,length, s)
{
// counts the occurrence of number which is odd
var countodd = 0;
for (var i = 0; i < length; i++) {
// if occurrence is odd
if (m.get(s.charCodeAt(i) - 48) & 1)
countodd++;
// if number exceeds 1
if (countodd > 1)
return false;
}
return true;
}
// function to print the largest palindromic number
// by permuting digits of a number
function largestPalindrome(s)
{
// string length
var l = s.length;
// map that marks the occurrence of a number
var m = new Map();
for (var i = 0; i < l; i++){
if (m.has(s.charCodeAt(i) - 48))
m.set(s.charCodeAt(i) - 48, m.get(s.charCodeAt(i) - 48)+1);
else
m.set(s.charCodeAt(i) - 48, 1);
}
// check the possibility of a palindromic number
if (possibility(m, l, s) == false) {
document.write("Palindrome cannot be formed");
return;
}
// string array that stores the largest
// permuted palindromic number
var largest = new Array(l);
// pointer of front
var front = 0;
// greedily start from 9 to 0 and place the
// greater number in front and odd in the
// middle
for (var i = 9; i >= 0; i--) {
// if the occurrence of number is odd
if (m.has(i) & 1) {
// place one odd occurring number
// in the middle
largest[Math.floor(l / 2)] = String.fromCharCode(i + 48);
// decrease the count
m.set(i, m.get(i)-1);
// place the rest of numbers greedily
while (m.get(i) > 0) {
largest[front] = String.fromCharCode(i + 48);
largest[l - front - 1] = String.fromCharCode(i + 48);
m.set(i, m.get(i)-2);
front++;
}
}
else {
// if all numbers occur even times,
// then place greedily
while (m.get(i) > 0){
// place greedily at front
largest[front] = String.fromCharCode(i + 48);
largest[l - front - 1] = String.fromCharCode(i + 48);
// 2 numbers are placed, so decrease the count
m.set(i, m.get(i)-2);
// increase placing position
front++;
}
}
}
// print the largest string thus formed
for (var i = 0; i < l; i++)
document.write(largest[i]);
}
// driver code
var s = "313551";
largestPalindrome(s);
// This code contributed by shubhamsingh10
</script>
Producción:
531135
Complejidad de tiempo : O (N), ya que estamos usando bucle para atravesar N veces.
Espacio auxiliar : O (N), ya que estamos usando espacio adicional para el mapa m y la array más grande .