Given a positive integer N, call it a Strong Number if the sum of the factorials of its decimal digits equals N.
Return "Yes" if N is a Strong Number and "No" otherwise.
Example 1
Input: N = 40585
Output: "Yes"
Explanation: The factorials add up to 4! + 0! + 5! + 8! + 5! = 24 + 1 + 120 + 40320 + 120 = 40585.
Example 2
Input: N = 10
Output: "No"
Explanation: The factorials add up to 1! + 0! = 1 + 1 = 2. The sum differs from 10.
Approach
Each digit contributes its factorial to the sum that must equal N. The digits can be read from right to left because their order does not affect the sum.
The remainder after division by 10 gives the last decimal digit. Integer division by 10 removes that digit and exposes the next one. Repeating these operations reads every digit exactly once, including zeros within the number.
Removing digits eventually reduces the working value to 0. A working copy is needed so the original N remains available for comparison with the final factorial sum. The number is a Strong Number exactly when that sum equals the original N.
Algorithm
Keep the original
N, make a working copy so the original value is available for the final comparison. Start the factorial sum at0.While the copy is positive, extract its last digit using the remainder after division by
10.Calculate the digit's factorial by starting at
1and multiplying by the integers from2through the digit. For0and1, the product stays1.Add the factorial to the sum and remove the last digit using integer division by
10. The scan ends when the copy reaches0, after one step for a single-digit input.Return
"Yes"if the sum equals the originalN. Otherwise, return"No".
Dry Run
Check if a Number is a Strong Number
Solution
#include <bits/stdc++.h>using namespace std;class Solution { // Returns the factorial of a decimal digit. int factorial(int digit) { int product = 1; // Multiply from 2 onward, leaving 0! and 1! equal to 1. for (int factor = 2; factor <= digit; factor++) { product *= factor; } return product; }public: // Returns "Yes" when N equals the sum of its digit factorials. string isStrongNumber(long long N) { long long remaining = N; long long sum = 0; // Extract and remove the rightmost digit each time. while (remaining > 0) { int digit = remaining % 10; sum += factorial(digit); remaining /= 10; } return sum == N ? "Yes" : "No"; }};// Driver codeint main() { long long N = 40585; // instance for class Solution Solution sol; cout << sol.isStrongNumber(N) << '\n'; return 0;}Complexity Analysis
Time Complexity: O(D), where D is the number of decimal digits in N, because each digit is extracted once and its factorial takes at most eight multiplications.
Space Complexity: O(1) auxiliary space because the calculation uses a fixed number of scalar values.
Interview follow-up Questions
Taking the remainder after division by 10 gives the last digit. Integer division by 10 removes that digit. Repeat these operations on a copy of N until it reaches 0, then compare the factorial sum with the original N.
Be the first to add a comment.