Check if a Number is a Strong Number

35
0

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 at 0.

  • While the copy is positive, extract its last digit using the remainder after division by 10.

  • Calculate the digit's factorial by starting at 1 and multiplying by the integers from 2 through the digit. For 0 and 1, the product stays 1.

  • Add the factorial to the sum and remove the last digit using integer division by 10. The scan ends when the copy reaches 0, after one step for a single-digit input.

  • Return "Yes" if the sum equals the original N. Otherwise, return "No".

Dry Run

Check if a Number is a Strong Number

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 code
int 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.

MathsTCS NQT

Read Similar Blogs

Comments0