Calculate Large Factorials Using Nodes in Java

Question

Okay, so I have been searching the internet and have found many things related to this question. However, I am not able to put the pieces together in order to figure this out.

The requirements are to calculate a large factorial (e.g. 999!) USING LINKED LISTS and NODES. There are many people online that have shown a basic way of calculating a factorial and I understand how to do the factorial part, but the part I am having trouble with is filling each node with an Int between 0-999 (a three digit number) then printing out each node to look like a whole number (including commas).

How can I achieve this? - My thoughts are to get the result of n! and just do %10, %100,etc.. to break it up and insert the parts into nodes, but that would be pointless because the factorial would have to be completely solved for that to work. So that would be dumb.

The reason for doing this is to learn how to manipulate nodes and linked lists for my Data Structures class.

To me, this a clear explanation, but please let me know if the question is unclear and I will try to explain. Any help will be much appreciated.

(I dont have any code to show besides a basic factorial function that I am using as a bases to build upon).

Answer 1

Okay, I think I understand what you're after.

At the end of this answer is a link to a Gist that solves this problem. I'm not entirely sure it's what you are after, alas... it's my best guess.

The algorithm consists of five steps:

1. Build the list of factorial members.
2. Calculate and group Prime Factors of factorial members.
3. Distribute Prime Factors over powers of 10.
4. Multiply Prime Factors, carrying overflow up into the next decimal place.
5. Print the solution.

It is inspired by the method described here on math.stackexchange.com. I strongly suggest reading both the question and answer linked before examining the Gist.

Now that that's been said, the Gist can be found here. It is very rough, meant only as a quick demonstration of the method.

I hope it helps you. Best of luck.

Answer 2

To calculate a factorial using a LinkedList is a simple 2-stage process.

Stage 1 is to create a LinkedList of all numbers up to the number you want the factorial of. This is a very simple operation that can be achieved with a basic for loop.

List<Integer> list = new LinkedList<Integer>();
for(int i = 1; i <= limit; i++) {
    list.add(i);
}
System.out.println(list);

Stage 2 is also relatively easy, using a foreach loop, we iterate over the contents of the list and multiply each element by the product of the previous list elements.

One major concern however, is that the factorial of numbers as large as 999 cannot be held in any of Java's primitive numeric types (int or even long). To hold the factorial, we have to make use of Java's BigDecimal class (Java Docs).

//Stage 2: Calculate the factorial.
BigDecimal factorial = new BigDecimal(1);
BigDecimal factor = null;
for(int n : list) {
    factor = new BigDecimal(n);
    factorial = factorial.multiply(factor);
}

With those two stages, we can simply print the contents of factorial to see the factorial of your provided number. See the complete code below:

public static void factorial(int limit) {
    // Stage 1: Build the list.
    List<Integer> list = new LinkedList<Integer>();
    for(int i = 1; i <= limit; i++) {
        list.add(i);
    }
    System.out.println(list);

    //Stage 2: Calculate the factorial.
    BigDecimal factorial = new BigDecimal(1);
    BigDecimal factor = null;
    for(int n : list) {
        factor = new BigDecimal(n);
        factorial = factorial.multiply(factor);
    }
    System.out.println(factorial);
}

Answer 3

We multiply like we actually do with every digit of the number and take take the carry forward. Each digit is stored in a node of the linkedlist. The number is stored in reverse order so that we can multiply without using any extra space.

public static void find(int n) {
Node head=new Node(1);

for(int i=2;i<=n;i++)
    multiply(i,head);

print(head);

}

private static void multiply(int k, Node head) {

int carry=0,prod=0;
Node prev=null;
while(head!=null)
{
    prod=head.data*k+carry;
    head.data=prod%10;
    carry=prod/10;
    prev=head;
    head=head.next;
}

while(carry!=0) {
    Node n=new Node(carry%10);
    prev.next=n;
    carry=carry/10;
    prev=prev.next;
}

}
private static void print(Node head) { //printing in reverse order
if(head==null)
    return;
print(head.next);
System.out.print(head.data);

}

The concept is best explained here