FCTRL2 - Editorial

editorial
, ,
1

Problem Link - Small factorials Practice Problem in 500 to 1000 difficulty problems

Problem Statement:

Given an integer n, calculate the factorial n! for a range of input numbers and print the result.

Approach:

  • Challenges in the Problem: Handling Large Numbers-
    • The value of n! grows extremely fast. For instance, 20! = 2,432,902,008,176,640,000. Standard data types such as int or long long cannot handle such large values since they exceed their maximum range.
  • Storing and Printing Large Numbers: To handle the large size of factorial results-
    • use an array to store individual digits of the factorial.
    • Perform multiplication digit by digit, handling carries like manual multiplication and store the result in reverse order for easier manipulation.

Steps:

  1. Use an Array to Store Digits:
  • To handle large results, use an array to store individual digits of the factorial. This avoids overflow issues with traditional data types.
  • Each digit of the resulting number is stored in an array in reverse order (least significant digit first) to simplify multiplication.
  1. Perform Multiplication Digit-by-Digit:
  • Use a manual multiplication approach, similar to how multiplication is done by hand:
    • Multiply each digit in the array by the current number x in the iteration.
    • Maintain a carry and add it to the next step to handle multi-digit results.
  • After multiplication, update the array with the new number and continue until n is reached.
  1. Print the Result:
  • After all iterations are complete, print the array starting from the highest index down to 0 to display the full factorial.

Complexity:

  • Time Complexity: O(n^2 . m), where m is the number of digits in the factorial. The approach is efficient for n up to 100 due to the manageable size of operations on individual digits.
  • Space Complexity: O(m), where m is the number of digits in the result (maximum for 100! is 158 digits).