A Krishnamurthy number is a number whose sum of the factorial of digits is equal to the number itself.
For example, 145 is the sum of the factorial of each digit.
1! + 4! + 5! = 1 + 24 + 120 = 145
Input : 145
Output : YES
Explanation: 1! + 4! + 5! =
1 + 24 + 120 = 145, which is equal to input,
hence YES.
Input : 235
Output : NO
Explanation: 2! + 3! + 5! =
2 + 6 + 120 = 128, which is not equal to input,
hence NO.
The idea is simple, we compute the sum of factorials of all digits and then compare the sum with n.
C++
#include <bits/stdc++.h>
using namespace std;
int factorial( int n)
{
int fact = 1;
while (n != 0) {
fact = fact * n;
n--;
}
return fact;
}
bool isKrishnamurthy( int n)
{
int sum = 0;
int temp = n;
while (temp != 0) {
sum += factorial(temp % 10);
temp = temp / 10;
}
return (sum == n);
}
int main()
{
int n = 145;
if (isKrishnamurthy(n))
cout << "YES" ;
else
cout << "NO" ;
return 0;
}
|
Java
import java.util.*;
import java.io.*;
class Krishnamurthy {
static int factorial( int n)
{
int fact = 1 ;
while (n != 0 ) {
fact = fact * n;
n--;
}
return fact;
}
static boolean isKrishnamurthy( int n)
{
int sum = 0 ;
int temp = n;
while (temp != 0 ) {
sum += factorial(temp % 10 );
temp = temp / 10 ;
}
return (sum == n);
}
public static void main(String[] args)
{
int n = 145 ;
if (isKrishnamurthy(n))
System.out.println( "YES" );
else
System.out.println( "NO" );
}
}
|
Python3
def factorial(n) :
fact = 1
while (n ! = 0 ) :
fact = fact * n
n = n - 1
return fact
def isKrishnamurthy(n) :
sum = 0
temp = n
while (temp ! = 0 ) :
rem = temp % 10
sum = sum + factorial(rem)
temp = temp / / 10
return ( sum = = n)
n = 145
if (isKrishnamurthy(n)) :
print ( "YES" )
else :
print ( "NO" )
|
C#
using System;
class GFG {
static int factorial( int n)
{
int fact = 1;
while (n != 0) {
fact = fact * n;
n--;
}
return fact;
}
static bool isKrishnamurthy( int n)
{
int sum = 0;
int temp = n;
while (temp != 0) {
sum += factorial(temp % 10);
temp = temp / 10;
}
return (sum == n);
}
public static void Main()
{
int n = 145;
if (isKrishnamurthy(n))
Console.Write( "YES" );
else
Console.Write( "NO" );
}
}
|
Javascript
<script>
function factorial(n)
{
let fact = 1;
while (n != 0)
{
fact = fact * n;
n--;
}
return fact;
}
function isKrishnamurthyNumber(n)
{
let sum = 0;
let temp = n;
while (temp != 0)
{
sum = sum + factorial(temp % 10);
temp = parseInt(temp / 10);
}
return sum == n;
}
let n = 145;
if (isKrishnamurthyNumber(n))
document.write( "YES" );
else
document.write( "NO" );
</script>
|
PHP
<?php
function factorial( $n )
{
$fact = 1;
while ( $n != 0)
{
$fact = $fact * $n ;
$n --;
}
return $fact ;
}
function isKrishnamurthyNumber( $n )
{
$sum = 0;
$temp = $n ;
while ( $temp != 0)
{
$sum = $sum + factorial( $temp % 10);
$temp = intdiv( $temp , 10);
}
return $sum == $n ;
}
$n = 145;
if (isKrishnamurthyNumber( $n ))
echo "YES" ;
else
echo "NO" ;
?>
|
Time Complexity: O(n log10n) where n is a given number
Auxiliary Space: O(1)
Interestingly, there are exactly four Krishnamurthy numbers i.e. 1, 2, 145, and 40585 known to us.
Approach 2: Precomputing factorials and checking each digit of the number against the precomputed factorials.
- The declaration int factorial[10]; creates an array factorial of 10 integers to store the precomputed factorials.
- The precomputeFactorials() function calculates and stores the factorials of numbers 0 to 9 in the factorial array. It uses a for loop to iterate through each number and calculates its factorial by multiplying it with the factorial of the previous number.
- The isKrishnamurthy(int n) function takes an integer n as input and checks if it is a Krishnamurthy number or not. It first declares a variable sum to store the sum of factorials of digits in n and a variable temp to store a copy of n.
- It then enters a while loop that continues until temp becomes zero. In each iteration of the loop, it calculates the rightmost digit of temp using the modulo operator (temp % 10) and adds the factorial of that digit to sum. It then updates the value of temp by removing the rightmost digit using integer division (temp /= 10).
- After the while loop completes, the function returns true if sum is equal to n, indicating that n is a Krishnamurthy number, or false otherwise.
- In the main() function, we call precomputeFactorials() to precompute the factorials of numbers 0 to 9 and store them in the factorial array.
- We then set n to 145, which is a Krishnamurthy number, and call isKrishnamurthy(n) to check if n is a Krishnamurthy number or not.
- Finally, we use cout to print “YES” if isKrishnamurthy(n) returns true, indicating that n is a Krishnamurthy number, or “NO” otherwise. We also use endl to insert a newline character after the output.
C++
#include <iostream>
using namespace std;
int factorial[10];
void precomputeFactorials() {
factorial[0] = 1;
for ( int i = 1; i < 10; i++) {
factorial[i] = i * factorial[i-1];
}
}
bool isKrishnamurthy( int n) {
int sum = 0;
int temp = n;
while (temp > 0) {
int digit = temp % 10;
sum += factorial[digit];
temp /= 10;
}
return (sum == n);
}
int main() {
precomputeFactorials();
int n = 145;
if (isKrishnamurthy(n)) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
return 0;
}
|
Java
import java.util.Arrays;
public class KrishnamurthyNumber {
static int [] factorial = new int [ 10 ];
public static void precomputeFactorials()
{
factorial[ 0 ] = 1 ;
for ( int i = 1 ; i < 10 ; i++) {
factorial[i] = i * factorial[i - 1 ];
}
}
public static boolean isKrishnamurthy( int n)
{
int sum = 0 ;
int temp = n;
while (temp > 0 ) {
int digit = temp % 10 ;
sum += factorial[digit];
temp /= 10 ;
}
return (sum == n);
}
public static void main(String[] args)
{
precomputeFactorials();
int n = 145 ;
if (isKrishnamurthy(n)) {
System.out.println( "YES" );
}
else {
System.out.println( "NO" );
}
}
}
|
Python3
factorial = [ 1 ] * 10
def precompute_factorials():
for i in range ( 1 , 10 ):
factorial[i] = i * factorial[i - 1 ]
precompute_factorials()
def is_krishnamurthy(n):
sum = 0
temp = n
while temp > 0 :
digit = temp % 10
sum + = factorial[digit]
temp / / = 10
return ( sum = = n)
n = 145
if is_krishnamurthy(n):
print ( "YES" )
else :
print ( "NO" )
|
C#
using System;
namespace KrishnamurthyNumber
{
class Program
{
static int [] factorial = new int [10];
static void precomputeFactorials()
{
factorial[0] = 1;
for ( int i = 1; i < 10; i++)
{
factorial[i] = i * factorial[i - 1];
}
}
static bool isKrishnamurthy( int n)
{
int sum = 0;
int temp = n;
while (temp > 0)
{
int digit = temp % 10;
sum += factorial[digit];
temp /= 10;
}
return (sum == n);
}
static void Main( string [] args)
{
precomputeFactorials();
int n = 145;
if (isKrishnamurthy(n))
{
Console.WriteLine( "YES" );
}
else
{
Console.WriteLine( "NO" );
}
}
}
}
|
Javascript
let factorial = [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880];
function precomputeFactorials() {
for (let i = 1; i < 10; i++) {
factorial[i] = i * factorial[i-1];
}
}
function isKrishnamurthy(n) {
let sum = 0;
let temp = n;
while (temp > 0) {
let digit = temp % 10;
sum += factorial[digit];
temp = Math.floor(temp / 10);
}
return (sum === n);
}
precomputeFactorials();
let n = 145;
if (isKrishnamurthy(n)) {
console.log( "YES" );
} else {
console.log( "NO" );
}
|
Time Complexity: O(logN)
Auxiliary Space: O(1)
Contact Us