Given an integer N and the task is to check whether N is a Factorion or not. A Factorion is a number which is equal to the sum of the factorials of its digits.
Examples:
Input: N = 40585
Output: Yes
4! + 0! + 5! + 8! + 5! = 40585
Input: N = 234
Output: No
2! + 3! + 4! = 32
Approach: Create an array fact[] of size 10 to store the factorials of all possible digits where fact[i] stores i!. Now for all the digits of the given number find the sum of factorials of the digits using the fact[] array computed earlier. If the sum if equal to the given number then the number is a Factorion else it is not.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;#define MAX 10// Function that returns true// if n is a Factorionbool isFactorion(int n){ // fact[i] will store i! int fact[MAX]; fact[0] = 1; for (int i = 1; i < MAX; i++) fact[i] = i * fact[i - 1]; // A copy of the given integer int org = n; // To store the sum of factorials // of the digits of n int sum = 0; while (n > 0) { // Get the last digit int d = n % 10; // Add the factorial of the current // digit to the sum sum += fact[d]; // Remove the last digit n /= 10; } if (sum == org) return true; return false;}// Driver codeint main(){ int n = 40585; if (isFactorion(n)) cout << "Yes"; else cout << "No"; return 0;} |
Java
// Java implementation of the above approachclass GFG { static int MAX = 10; // Function that returns true // if n is a Factorion static boolean isFactorion(int n) { // fact[i] will store i! int fact[] = new int[MAX]; fact[0] = 1; for (int i = 1; i < MAX; i++) fact[i] = i * fact[i - 1]; // A copy of the given integer int org = n; // To store the sum of factorials // of the digits of n int sum = 0; while (n > 0) { // Get the last digit int d = n % 10; // Add the factorial of the current // digit to the sum sum += fact[d]; // Remove the last digit n /= 10; } if (sum == org) return true; return false; } // Driver code public static void main (String[] args) { int n = 40585; if (isFactorion(n)) System.out.println("Yes"); else System.out.println("No"); } }// This code is contributed by AnkitRai01 |
Python3
# Python3 implementation of the approach MAX = 10# Function that returns true # if n is a Factorion def isFactorion(n) : # fact[i] will store i! fact = [0] * MAX fact[0] = 1 for i in range(1, MAX) : fact[i] = i * fact[i - 1] # A copy of the given integer org = n # To store the sum of factorials # of the digits of n sum = 0 while (n > 0) : # Get the last digit d = n % 10 # Add the factorial of the current # digit to the sum sum += fact[d] # Remove the last digit n = n // 10 if (sum == org): return True return False# Driver code n = 40585if (isFactorion(n)): print("Yes") else: print("No") # This code is contributed by# divyamohan123 |
C#
// C# implementation of the above approachusing System;class GFG { static int MAX = 10; // Function that returns true // if n is a Factorion static bool isFactorion(int n) { // fact[i] will store i! int [] fact = new int[MAX]; fact[0] = 1; for (int i = 1; i < MAX; i++) fact[i] = i * fact[i - 1]; // A copy of the given integer int org = n; // To store the sum of factorials // of the digits of n int sum = 0; while (n > 0) { // Get the last digit int d = n % 10; // Add the factorial of the current // digit to the sum sum += fact[d]; // Remove the last digit n /= 10; } if (sum == org) return true; return false; } // Driver code public static void Main (String[] args) { int n = 40585; if (isFactorion(n)) Console.WriteLine("Yes"); else Console.WriteLine("No"); } }// This code is contributed by Mohit kumar |
Javascript
<script>// Javascript implementation of the approachconst MAX = 10;// Function that returns true// if n is a Factorionfunction isFactorion(n){ // fact[i] will store i! let fact = new Array(MAX); fact[0] = 1; for (let i = 1; i < MAX; i++) fact[i] = i * fact[i - 1]; // A copy of the given integer let org = n; // To store the sum of factorials // of the digits of n let sum = 0; while (n > 0) { // Get the last digit let d = n % 10; // Add the factorial of the current // digit to the sum sum += fact[d]; // Remove the last digit n = parseInt(n / 10); } if (sum == org) return true; return false;}// Driver code let n = 40585; if (isFactorion(n)) document.write("Yes"); else document.write("No");</script> |
Output:
Yes
Time Complexity: O(log10n)
Auxiliary Space: O(MAX)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
