|
Given a number N, output all Munchhausen numbers from 1 to n.
Introduction : A Münchhausen number is a number equal to the sum of its digits raised to each digit’s power. It is similar to that of Narcissistic Number.
For example:
3435 = 33 + 44 + 33 + 55
One can also be considered as Münchhausen Number because when 1 raised to the power 1 is 1 itself.
Since, the number 3435 can be expressed as sum of each digits of the number when each digits of the numbers are raised to power equivalent to the digits itself i.e., ((3 raised to the power 3) + (4 raised to the power 4) + (3 raised to the power 3) + (5 raised to the power 5)) will give output to the same number i.e. 3435, then the number can be called as Münchhausen Number.
Example:
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.
We precompute i raised to power i for every possible digit i where i varies from 0 to 9. After precomputing these values, we traverse through all digits of every number smaller than equal to n and compute sum of digit raised to power digit.
C++
<?php
$pwr = array_fill(0, 10, 0);
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;
for ($i = 0; $i < 10; $i++)
$pwr[$i] = pow((float)($i), (float)($i));
for ($i = 1; $i < $n + 1; $i++)
if (isMunchhausen($i))
print($i . "\n");
}
$n = 10000;
printMunchhausenNumbers($n);
?>
|
Javascript
<script>
var pwr;
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);
for(var i = 0; i < 10; i++)
pwr[i] = Math.pow(i, i);
for(var i = 1; i <= n; i++)
if (isMunchhausen(i) == true)
document.write(i + "<br>");
}
var n = 10000;
printMunchhausenNumbers(n);
</script>
|
Output:
1
3435
Time complexity: O(n logn) n for outer for loop and log n for while loop in function isMunchhausen
Auxiliary space: O(1) because it is using constant space for array pow
Note : If the definition 0^0 = 0 is adopted, then there are exactly four Münchhausen numbers: 0, 1, 3435, and 438579088 [Source : MathWorld]
|
