Doubt in approach

#1

Hello, I know that 500 factorial has 1135 digits and we can’t store these digits in our long long int we need an array for storing these much of digits. But I was thinking that if somehow I get the number of digits of my factorial then I will use that number of boxes in that array to store the digits ? How should I proceed with the most optimized way ? Please help.

#2

i did not get your approach exactly how will you implement it??

The following is a detailed algorithm for finding factorial.

factorial(n)

  1. Create an array ‘res[]’ of MAX size where MAX is number of maximum digits in output.
  2. Initialize value stored in ‘res[]’ as 1 and initialize ‘res_size’ (size of ‘res[]’) as 1.
  3. Do following for all numbers from x = 2 to n.
    ……a) Multiply x with res[] and update res[] and res_size to store the multiplication result.

How to multiply a number ‘x’ with the number stored in res[]?
The idea is to use simple school mathematics. We one by one multiply x with every digit of res[]. The important point to note here is digits are multiplied from rightmost digit to leftmost digit. If we store digits in same order in res[], then it becomes difficult to update res[] without extra space. That is why res[] is maintained in reverse way, i.e., digits from right to left are stored.

multiply(res[], x)

  1. Initialize carry as 0.
  2. Do following for i = 0 to res_size – 1
    ….a) Find value of res[i] * x + carry. Let this value be prod.
    ….b) Update res[i] by storing last digit of prod in it.
    ….c) Update carry by storing remaining digits in carry.
  3. Put all digits of carry in res[] and increase res_size by number of digits in carry.
1 Like
#3
  1. Create an array ‘res[]’ of MAX size where MAX is number of maximum digits in output.

Yes I want to create a function which firstly calculates the number of digits and returns the number of digits to the factorial function. Because I want to use that as max size of array. So, how do I calculate the number of digits?

#4

MAX is not the exact no of digits in factorial of N
MAX is the max no of digits can come in your output
it is just to make the array
you can take any value b/w 500 to1000

#5

Ok Thank you :slightly_smiling_face: