Número de Münchhausen

Dado un número N, genera todos los números de Munchhausen del 1 al n.
Introducción: Un número de Münchhausen es un número igual a la suma de sus dígitos elevados a la potencia de cada dígito. Es similar a la del Número Narcisista .

Por ejemplo: 
3435 = 3 ³ + 4 ⁴ + 3 ³ + 5 ⁵
Uno también puede ser considerado como Número de Münchhausen porque cuando 1 elevado a la potencia 1 es 1 mismo.
Dado que el número 3435 se puede expresar como la suma de cada dígito del número cuando cada dígito de los números se eleva a una potencia equivalente a los dígitos mismos, es decir, ((3 elevado a la potencia 3) + (4 elevado a la potencia 4 ) + (3 elevado a la potencia 3) + (5 elevado a la potencia 5)) dará salida al mismo número, es decir, 3435, entonces el número puede llamarse Número de Münchhausen.

Ejemplo: 

Input : 500
Output : 1
One is the only Münchhausen Number smaller
than or equal to 500.

Input : 5000
Output : 1  3435
1 and 3435 are the only Münchhausen Numbers smaller
than or equal to 5000.

Precalculamos i elevado a i para cada dígito posible i donde i varía de 0 a 9. Después de precalcular estos valores, recorremos todos los dígitos de cada número menor que n y calculamos la suma del dígito elevado a dígito de potencia.

// C++ code for Münchhausen Number
#include <bits/stdc++.h>
using namespace std;
 
// pwr[i] is going to store i raised to
// power i.
unsigned pwr[10];
 
// Function to check out whether
// the number is Münchhausen
// Number or not
bool isMunchhausen(unsigned n) {
    unsigned sum = 0;
    int temp = n;
 
    while (temp) {
        sum += pwr[(temp % 10)];
        temp /= 10;
    }
 
    return (sum == n);
}
 
void printMunchhausenNumbers(int n)
{
    // Precompute i raised to power i for every i
    for (int i = 0; i < 10; i++ )
        pwr[i] = (unsigned)pow( (float)i, (float)i );
     
    // The input here is fixed i.e. it will
    // check up to n
    for (unsigned i = 1; i <= n; i++)
 
        // check the integer for Münchhausen Number,
        // if yes then print out the number
        if (isMunchhausen(i))
            cout << i << "\n";
}
 
// Driver Code
int main() {
    int n = 10000;
    printMunchhausenNumbers(n);
    return 0;
}

// Java code for Munchhausen Number
 
import java.io.*;
import java.util.*;
 
class GFG {
// pwr[i] is going to store i raised to
// power i.
static long[] pwr;
  
// Function to check out whether
// the number is Munchhausen
// Number or not
static Boolean isMunchhausen(int n) {
    long sum = 0l;
    int temp = n;
  
    while (temp>0) {
        int index= temp%10;
        sum =sum + pwr[index];
        temp /= 10;
    }
  
    return (sum == n);
}
  
static void printMunchhausenNumbers(int n)
{
    pwr= new long[10];
 
    // Precompute i raised to
    // power i for every i
    for (int i = 0; i < 10; i++ )
        pwr[i] = (long)Math.pow( (float)i, (float)i );
      
    // The input here is fixed i.e. it will
    // check up to n
    for (int i = 1; i <= n; i++)
  
        // check the integer for Munchhausen Number,
        // if yes then print out the number
        if (isMunchhausen(i)==true)
            System.out.println(i );
}
    public static void main (String[] args) {
    int n = 10000;
    printMunchhausenNumbers(n);
     }
}
// This code is contributed by Gitanjali.

# Python 3 code for
# Münchhausen Number
import math
 
# pwr[i] is going to
# store i raised to
# power i.
pwr = [0] * 10
 
# Function to check out
# whether the number is
# Münchhausen Number or
# not
def isMunchhausen(n) :
 
    sm = 0
    temp = n
 
    while (temp) :
        sm= sm + pwr[(temp % 10)]
        temp = temp // 10
     
    return (sm == n)
 
def printMunchhausenNumbers(n) :
 
    # Precompute i raised to
    # power i for every i
    for i in range(0, 10) :
        pwr[i] = math.pow((float)(i), (float)(i))
     
    # The input here is fixed
    # i.e. it will check up to n
    for i in range(1,n+1) :
         
        # check the integer for
        # Münchhausen Number, if
        # yes then print out the
        # number
        if (isMunchhausen(i)) :
            print( i )
 
 
# Driver Code
n = 10000
printMunchhausenNumbers(n)
 
# This code is contributed by Nikita Tiwari.

// C# code for Munchhausen Number
using System;
 
class GFG {
 
    // pwr[i] is going to store i
    // raised to power i.
    static long[] pwr;
 
    // Function to check out whether
    // the number is Munchhausen
    // Number or not
    static bool isMunchhausen(int n)
    {
        long sum = 0;
        int temp = n;
 
        while (temp > 0) {
            int index = temp % 10;
            sum = sum + pwr[index];
            temp /= 10;
        }
 
        return (sum == n);
    }
 
    static void printMunchhausenNumbers(int n)
    {
        pwr = new long[10];
 
        // Precompute i raised to
        // power i for every i
        for (int i = 0; i < 10; i++)
            pwr[i] = (long)Math.Pow((float)i, (float)i);
 
        // The input here is fixed i.e.
        // it will check up to n
        for (int i = 1; i <= n; i++)
 
            // check the integer for Munchhausen Number,
            // if yes then print out the number
            if (isMunchhausen(i) == true)
                Console.WriteLine(i);
    }
     
    // Driver Code
    public static void Main()
    {
        int n = 10000;
        printMunchhausenNumbers(n);
    }
}
 
// This code is contributed by vt_m.

<?php
// PHP code for Münchhausen Number
 
// pwr[i] is going to store i raised
// to power i.
$pwr = array_fill(0, 10, 0);
 
// Function to check out whether the
// number is Münchhausen Number or not
function isMunchhausen($n)
{
    global $pwr;
    $sm = 0;
    $temp = $n;
 
    while ($temp)
    {
        $sm= $sm + $pwr[($temp % 10)];
        $temp = (int)($temp / 10);
    }
    return ($sm == $n);
}
 
function printMunchhausenNumbers($n)
{
    global $pwr;
     
    // Precompute i raised to power
    // i for every i
    for ($i = 0; $i < 10; $i++)
        $pwr[$i] = pow((float)($i), (float)($i));
     
    // The input here is fixed i.e. it
    // will check up to n
    for ($i = 1; $i < $n + 1; $i++)
         
        // check the integer for Münchhausen
        // Number, if yes then print out the
        // number
        if (isMunchhausen($i))
            print($i . "\n");
}
 
// Driver Code
$n = 10000;
printMunchhausenNumbers($n);
 
// This code is contributed by mits
?>

<script>
 
// Javascript code for Munchhausen Number
// pwr[i] is going to store i raised to
 
// power i.
var pwr;
  
// Function to check out whether
// the number is Munchhausen
// Number or not
function isMunchhausen(n)
{
    var sum = 0;
    var temp = n;
  
    while (temp > 0)
    {
        var index= temp % 10;
        sum =sum + pwr[index];
        temp = parseInt(temp / 10);
    }
    return (sum == n);
}
  
function printMunchhausenNumbers(n)
{
    pwr = Array.from({length: 10}, (_, i) => 0);
 
    // Precompute i raised to
    // power i for every i
    for(var i = 0; i < 10; i++)
        pwr[i] = Math.pow(i, i);
      
    // The input here is fixed i.e. it will
    // check up to n
    for(var i = 1; i <= n; i++)
  
        // check the integer for Munchhausen Number,
        // if yes then print out the number
        if (isMunchhausen(i) == true)
            document.write(i + "<br>");
}
 
// Driver code
var n = 10000;
 
printMunchhausenNumbers(n);
 
// This code is contributed by Princi Singh
 
</script>

Producción: 

1
3435

Complejidad de tiempo : O(n logn) n for outside for loop y log n for while loop en la función isMunchhausen

Nota: si se adopta la definición 0^0 = 0, entonces hay exactamente cuatro números de Münchhausen: 0, 1, 3435 y 438579088 [Fuente: MathWorld ]