Krishnamurthy Number in Java
A Krishnamurthy number, also known as a Strong number, is a special type of number in which the sum of the factorials of its digits is equal to the number itself. In other words, if a number 'n' has 'm' digits, and the sum of the factorials of each digit is equal to 'n', then it is called a Krishnamurthy number.
Example 1:
Input:145
Explanation: To check if 145 is a Krishnamurthy Number we have to calculate the factorial sum of its digits as follows:
- digit = 5, factorial(digit) = 120
- digit = 4, factorial(digit) = 24
- digit = 1, factorial(digit) = 1
So, the sum of the factorials of its digits is 120 + 24 + 1 = 145, which is the same as the original number.
Therefore, 145 is a Krishnamurthy Number.
Example 2:
Input: 40585
Explanation: To check if 40585 is a Krishnamurthy Number we have to calculate the factorial sum of its digits as follows:
- digit = 5, factorial(digit) = 120
- digit = 8, factorial(digit) = 40320
- digit = 5, factorial(digit) = 120
- digit = 0, factorial(digit) = 1
- digit = 4, factorial(digit) = 24
So, the sum of the factorials of its digits is 120 + 40320 + 120 + 1 + 24 = 40585, which is the same as the original number.
Therefore, 40585 is also a Krishnamurthy Number.
Implementation: Using Normal Approach
ALGORITHM:
Step 1: Take the input number from the user and store it in a variable.
Step 2: Calculate the factorial of each digit in the number and add them together.
Step 3: Compare the sum with the original number. If they are equal, then the number is a Krishnamurthy number; otherwise, it is not.
FileName: KrishnamurthyNumber .java
import java.util.*;
public class KrishnamurthyNumber {
public static void main(String[] args) {
// example 1: 145
int number1 = 145; // number to be checked
int sum1 = 0; // initialize sum to 0
int temp1 = number1; // store the original number
// calculate factorial sum of digits
while(number1 > 0) {
int digit1 = number1 % 10; // get the last digit of the number
sum1 += factorial(digit1); // add the factorial of the digit to the sum
number1 /= 10; // remove the last digit from the number
}
// check if the number is a Krishnamurthy Number
if(sum1 == temp1) {
System.out.println(temp1 + " is a Krishnamurthy Number");
}
else {
System.out.println(temp1 + " is not a Krishnamurthy Number");
}
// example 2: 40585
int number2 = 40585; // number to be checked
int sum2 = 0; // initialize sum to 0
int temp2 = number2; // store the original number
// calculate factorial sum of digits
while(number2 > 0) {
int digit2 = number2 % 10; // get the last digit of the number
sum2 += factorial(digit2); // add the factorial of the digit to the sum
number2 /= 10; // remove the last digit from the number
}
// check if the number is a Krishnamurthy Number
if(sum2 == temp2) {
System.out.println(temp2 + " is a Krishnamurthy Number");
}
else {
System.out.println(temp2 + " is not a Krishnamurthy Number");
}
}
/**
* A function to calculate the factorial of a given number.
* Returns 1 if the number is 0 or 1.
*/
public static int factorial(int n) {
if(n == 0 || n == 1) {
return 1;
}
else {
int result = 1;
for(int i = 2; i <= n; i++) {
result *= i;
}
return result;
}
}
}
Output:
145 is a Krishnamurthy Number
40585 is a Krishnamurthy NumberComplexity Analysis:
Time Complexity: The time complexity of this program is O(d * n), where d is the number of digits in the input number and n is the maximum value of a single digit Here the program iterates through each digit of the input number and performs a factorial calculation, which takes O(n) time.
Space Complexity: The space complexity of this program is O(1), as it only uses a fixed amount of memory to store the input number, the sum of factorials, and temporary variables used in the calculations. The space used is not dependent on the size of the input number.
Implementation: Using Recursion
ALGORITHM:
Step 1: If n is equal to zero, return true
Step 2: Compute the factorial of the last digit of n
Step 3: Add the factorial to the result of a recursive call to the function with the remaining digits of n
Step 4: Check if the sum is equal to n
Step 5: If the sum is equal to n, return true
Step 6: Otherwise, return false
FileName: KrishnamurthyNumber.java
import java.util.*;
public class KrishnamurthyNumber {
public static void main(String[] args) {
// example 1: 145
int number1 = 145; // number to be checked
// check if the number is a Krishnamurthy Number
if(isKrishnamurthy(number1)) {
System.out.println(number1 + " is a Krishnamurthy Number");
}
else {
System.out.println(number1 + " is not a Krishnamurthy Number");
}
// example 2: 40585
int number2 = 40585; // number to be checked
// check if the number is a Krishnamurthy Number
if(isKrishnamurthy(number2)) {
System.out.println(number2 + " is a Krishnamurthy Number");
}
else {
System.out.println(number2 + " is not a Krishnamurthy Number");
}
}
/**
* A recursive function to calculate the factorial of a given number.
* Returns 1 if the number is 0 or 1.
*/
public static int factorial(int n) {
if(n == 0 || n == 1) {
return 1;
}
else {
return n * factorial(n-1);
}
}
/**
* A recursive function to check if a given number is a Krishnamurthy Number.
* Returns true if the sum of the factorials of the digits is equal to the number itself.
*/
public static boolean isKrishnamurthy(int n) {
// Calculate the number of digits in the number
int numDigits = (int) Math.log10(n) + 1;
int sum = 0;
int temp = n;
while (temp != 0) {
int digit = temp % 10;
sum += factorial(digit);
temp /= 10;
}
return sum == n;
}
}Output:
145 is a Krishnamurthy Number
40585 is a Krishnamurthy NumberComplexity Analysis:
Time Complexity: The time complexity of this recursive approach is O(n log n), where n is the number of digits in the input number. Here each digit in the number has to be processed, and for each digit, the factorial function is called, which has a time complexity of O(n).
Space Complexity: The space complexity is also O(n) due to the recursion stack, as each recursive call requires additional space on the stack.
Implementation: Using Iterative Approach
ALGORITHM:
Step 1: Set sum to 0
Step 2: Set num to n
Step 3: While num > 0, do the following:
Step 3.1: Get the last digit of num using num % 10
Step 3.2: Compute the factorial of the digit using a for loop
Step 3.3: Add the factorial to sum
Step 3.4: Remove the last digit from num using num /= 10
Step 4: If sum equals n, return true
Step 5: Otherwise, return false
FileName: KrishnamurthyNumber.java
import java.util.*;
public class KrishnamurthyNumber {
public static boolean isKrishnamurthy(int n) {
int sum = 0;
int num = n;
// Iterate over each digit of the input number
while (num > 0) {
int digit = num % 10;
int factorial = 1;
// Compute the factorial of the current digit
for (int i = 2; i <= digit; i++) {
factorial *= i;
}
// Add the factorial to the sum
sum += factorial;
num /= 10;
}
// Check if the sum is equal to the original input number
return sum == n;
}
public static void main(String[] args) {
// Examples
int n1 = 145;
int n2 = 40585;
System.out.println(n1 + " is a Krishnamurthy number: " + isKrishnamurthy(n1));
System.out.println(n2 + " is a Krishnamurthy number: " + isKrishnamurthy(n2));
}
}Output:
145 is a Krishnamurthy number: true
40585 is a Krishnamurthy number: trueComplexity Analysis:
Time Complexity: O(n log n) - The while loop iterates once for each digit in n and the for loop computes the factorial of each digit, which takes O(log n) time. Therefore, the time complexity is O(n log n).
Space Complexity: O(1) - The space used by the algorithm is constant and does not depend on the input size, so the space complexity is O(1).