Broken calculator problem

#1

can anyone please explain me the solution of this question>
i unlocked its editorial and i am not able to understand what has been done in the code and what is the problem with normal factorial function?

#2

Hello @alankrit.agr99,

Approach:
factorial()

  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.
    … Multiply x with res[] and update res[] and res_size to store the multiplication result.
  4. Print res[] from right to left.

easy?:wink:

Algorithm for multiplication:

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.

Hope, this would help.
Give a like if you are satisfied.

#3

you have just copied the solution.
i am not able to understand what is done in this solution thats why only i posted this doubt

1 Like
#4

Hi @alankrit.agr99 ,
Since constraints are small, one obvious solution would be to use python and get AC :wink:
Now coming to C++ solution, as we know long long int can store integer upto max 10^18. So, you must have got the idea that we should do all operations using string, now suppose we were given a function F(x,y) (where ‘x’ and ‘y’ are strings as parameters) which return string representing the multiplication of x and y.
Now what we have to do now is just:
string ans=“1”;
for(int i=2;i<=n;i++){
string ii=to_string(i);
ans=F(ans,ii);
}
And, ans will be your final answer.
Now the question is how to multiply two big integers represented as strings.
You know how to multiply two large numbers by hand, ie long multiplication? That’s just an algorithm. Turn it into code. Use arrays to hold the digits. If you want to multiply 100 digit numbers together, use arrays that hold 100 numbers for the two numbers and 200 digits for the product. Or see how big the numbers are, then pick array sizes of a suitable size.

You might want to start with adding two 100 digit numbers together because the standard algorithm for long multiplication includes adding numbers together, so you have to do it anyway and as it is so simple it is a good place to start.

Well if you still have any doubt, please do ask.

Thanks,

#5

Hey @alankrit.agr99 ,

So, let’s understand it with the help of an example:
Relate the approach with the way you perform multiplication in mathematics.

Why are we using a matrix?
The factorial results in a value greater than the range of long long.
Example:
Input :50
Output : 30414093201713378043612608166064768844377641568960512000000000000

Let’s understand the logic for multiplication using a small example:
76*4

  1. In mathematics:
    76
    x4
    __
    304

    After multiplying 4 with 6 the result is 24
    adding carry to it i.e. 0 initially. So, the result is 24 only.
    So, write the last digit as it is i.e. 4
    Then, take 2 as carry over 7.

    Now multiplying 4 with 7, the result is 28
    Add carry to it 28+2=30
    Write the last digit as it is i.e. 0
    And take 3 as carry.

    As there are no more digits left to multiply with 4.
    So, write carry as it is in the answer i.e. 3.
    Hence, the answer is 304

Now, the same approach has been followed in the code.
The only difference is. The result here is stored from right to left.
In the case of the array, it will be stored from left to right

  1. With array:

    Create an array of size 1000: int res[10000];
    Initially res[] stores 76 as res[0]=6 and res[1]=7 (the digit at one’s place is at index 0)
    add res_size=2;
    //initialize carry to zero
    carry=0;
    Now multiply res[] with 4:

    for i=0 to res_size-1:
    2.1. i=0:
    prod=res[i]4+carry=64+0=24
    res[i]=res%10=4 (gives the digit at one’s place)
    carry=res/10=2 (rest goes to carry)
    2.2. i=1:
    prod=res[i]4+carry=74+2=30
    res[i]=res%10=0 (gives the digit at one’s place)
    carry=res/10=3 (rest goes to carry)
    End loop

    \\insert carry to the res[]
    while(carry>0)
    res[res_size++]=c%10=3;
    c=c/10=0;
    end loop

This is how the multiplication is happening in the logic that i have specified in my previous reply.

Note:
As result in array is stored from left to right in res[].
So, print res from right to left i.e. from index res_size-1 to 0.

Hope, this would help.
Give a like if you are satisfied.

#6

@S18ML0016
I am not the one who asked :roll_eyes:

#7

@abhishek.171co203,

That was a mistake…:sweat_smile::rofl:

1 Like
#8

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

1 Like