Vivek was roaming around in the electronics shop, where he saw a box called as BlackBox.…
- User
Vivek was roaming around in the electronics shop, where he saw a box called as BlackBox. He was intrigued by its function, so he bought it. It's functionality states that for given integer input N ≤ 1000 - it outputs the sum of all the digits in factorial of N (N!).
Now Vivek wants to extend its functionality for large numbers. So, he wants you to write a program that can check the correctness of the BlackBox .
INPUT :
The first line of the input contains a single integer T ( the number of test cases ). Next T lines of input contains an integer N .
OUTPUT :
For each test case, print the sum of all digits in the factorial of the corresponding input integer.
CONSTRAINTS :
1 ≤ T ≤ 10^3
0 ≤ N ≤ 1000
SAMPLE INPUT 5 1 2 3 4 5
SAMPLE OUTPUT 1 2 6 6 3
Explanation
for test 1, N=1 , factorial of N = 1 , sum of digits = 1. for test 2, N=2 , factorial of N = 2 , sum of digits = 2. for test 3, N=3 , factorial of N = 6 , sum of digits = 6. for test 4, N=4 , factorial of N = 24 , sum of digits = 6. for test 5, N=5 , factorial of N = 120 , sum of digits = 3.
Assistant
We need to compute sum of digits of N! for N up to 1000, multiple test cases up to 1000. So N! is huge, but we can compute it exactly using big integers (e.g., Python's arbitrary precision) or precompute factorials and then sum digits. However, N up to 1000, factorial has about 2568 digits (1000! ~ 4.02e2567). That's fine in Python; we can compute directly.
But maybe they want a more efficient approach? Since constraints are modest, we can precompute all factorials from 0 to 1000 and store digit sums. Or compute on the fly per test case. T up to 1000, each factorial computation from scratch may be okay, but precomputation is more efficient.
We'll implement:
- Precompute fact[0] = 1.
- For i in range(1, 1001): fact[i] = fact[i-1] * i.
- Then for each N, compute sum(int(d) for d in str(fact[N])).
But we need to be careful about memory: fact[1000] is a huge integer, storing all 1001 factorials may take some memory but it's okay in Python (each big int object holds digits). Alternatively, we could compute digit sum on the fly during multiplication? Not necessary.
Edge case: N=0, factorial is 1, sum=1.
We'll produce code accordingly.
Now produce answer: Python function solve() reading from stdin, writing to stdout.
Check sample: 1->1,2->2,3->6,4->6,5->3.
Let's implement.
But there is a nuance: The problem statement says "BlackBox outputs the sum of all the digits in factorial of N" and "Vivek wants to extend its functionality for large numbers." So we need to compute for N up to 1000. In sample, N=5 gives sum=3 (1+2+0). Good.
We'll produce final answer.
We must ensure speed: precomputation using Python's integer multiplication is fine.
We can also compute digit sums without converting to string by repeated division by 10, but conversion is fine.
Thus final code:
import sys
def precompute(): fact = [1] for i in range(1, 1001): fact.append(fact[-1] * i) return fact
def main(): data = sys.stdin.read().strip().split() if not data: return t = int(data[0]) nums = list(map(int, data[1:])) facts = precompute() out_lines = [] for n in nums[:t]: s = str(facts[n]) digit_sum = sum(int(ch) for ch in s) out_lines.append(str(digit_sum)) sys.stdout.write("\n".join(out_lines))
if name == "main": main()
That's it.
But the problem says T ≤ 10^3, N ≤ 1000, so it's okay.
I'll output the solution. ```python
import sys
Precompute factorials from 0 to 1000
def precompute_factorials(limit: int): fact = [1] * (limit + 1) # fact[0] = 1 for i in range(1, limit + 1): fact[i] = fact[i-1] * i return fact
def solve() -> None: data = sys.stdin.read().strip().split() if not data: return t = int(data[0]) nums = list(map(int, data[1:])) # Since t may be less than len(nums) we only use the first t values nums = nums[:t]
MAX_N = 1000 facts = precompute_factorials(MAX_N) out_lines = [] for n in nums: # Compute sum of digits of facts[n] digit_sum = sum(int(ch) for ch in str(facts[n])) out_lines.append(str(digit_sum)) sys.stdout.write("\n".join(out_lines))if name == "main": solve()