Java: Please explain this code in detail for me.

Question

this question is related to this post: https://stackoverflow.com/a/35810542/5888956

Basically, I have to write a program that reads in the integer from the keyboard, and it has to be able to display 50! using only array. (cannot use Biginteger or anything) I got this so far, thanks to the help from the previous post.

import java.util.Scanner;
class Factorial
{
    public static void main(String[] args)
    {
        int n;

        Scanner kb = new Scanner(System.in);
        System.out.println("Enter n");
        n = kb.nextInt();
        int [] result = fact(n);

        int i = result.length-1;
        while (i > 0 && result[i] == 0)
        {
            i--; 
        }

        System.out.print(n + "! = ");
        while (i >= 0)
        {
            System.out.print(result[i--]);
        }

        System.out.println();
    }

    public static int[] fact(int n)
    {

        int[] a = new int[100];
        a[0] = 1;



        for (int i = 1; i <= n; i++)
        {
            int carry = 0;
            for(int j = 0; j < a.length; j++)
            {
                int x = a[j] * i + carry;
                a[j] = x % 10;
                carry = x / 10;             
            }

        }

        return a;
    }
}

But I can't still understand the logic behind here. Especially, this part,

for (int i = 1; i <= n; i++)
{
      int carry = 0;
      for(int j = 0; j < a.length; j++)
      {
           int x = a[j] * i + carry;
           a[j] = x % 10;
           carry = x / 10;             
      }
}

I'm trying to solve this with pen and paper, so that I can understand it completely. (of course with the small number like 4!) So if I type 4 for n, 4! is 24 (4*3*2*1). In my logic, when i is 1 a[0] is 1 because I initialized above, but after the for loop ends once, does it become 0?

i = 1, j = 0
x = a[0] * 1 + 0 = 1
a[0] = 0
carry = 1
// ------repeat the loop
i = 2, j = 0
x = a[0] * 1 + 1 = 1
a[0] = 0
carry = 1

So it is apparently not the right logic, I think. Can someone please please help me to understand this?

Answer 1

The factorial operation just means multiplying a whole bunch of numbers, so conceptually, it is not a difficult operation to implement. The reason why it quickly becomes a problem when implementing in code, is that it produces huge numbers, in fact, too large to be held in one int (4 bytes) or even long (8 bytes) variables (12! is the max you could hold in an int). Otherwise, we would just do something like:

int fact = 1;
for(int i = 2 ; i <= n ; i++) {
    fact *= i;
}

So one way to deal with this is to treat a number as an "array of digits", in base 10. For example, the number 2016 could be treated like this array: int[] digits = {2, 0, 1, 6}, which is just another way of saying 2016 = 2*1000 + 0*100 + 1*10 + 6*1.

Now let's imagine that we have 8-bits computers, and we can't represent numbers larger than 255 (or pow(2,8)-1). We wouldn't be able to simply do 2016*2 directly, but, because multiplication is distributive a(b+c) = ab+ac, we could decompose the multiplication of the "large" number 2016 into smaller multiplications like so:
2016 → {2, 0, 1, 6} → 2*1000 + 0*100 + 1*10 + 6
2016 * 2 = (2*1000 + 0 + 1*10 + 6) * 2 = (2*2)*1000 + (2*0) + (2*1)*10 + (2*6)

Now we can do these small multiplications like you would by hand:
2016 * 2 → {2, 0, 1, 6} * 2 → {2*2, 0*2, 1*2, 6*2} → {4, 0, 2, 12}

We get 12 for the first digit, so we need the carry over the 1:
{4, 0, 2, 12} → {4, 0, 2+1, 2} → {4, 0, 3, 2} = 4032

That's exactly what your code does:

a[0] = 1;
for (int i = 1; i <= n; i++) {
    int carry = 0;
    for(int j = 0; j < a.length; j++) {
        int x = a[j] * i + carry;
        a[j] = x % 10;
        carry = x / 10;             
    }
}

It takes your number or "array of digits" a, and multiplies the digits a[j] individually by i → x = a[j] * i. If it's bigger than 9, take the extra to carry it to the next digit → carry = x / 10, and you're left with the remnant as the value of the digit → a[j] = x % 10.