Why does my factorial program print 0?

Question

This code is meant to find 100 factorial and the sum the digits in the number. However, it returns 0.

Why does this happen?

public class Problem20 {
  public static void main(String[] args){
    int num = 100;

    for(int i = 1; i< 100; i++){
        num = num * i;
    }

    String numstring = Integer.toString(num);
    int sum = 0;

    for(int j = 0; j < numstring.length(); j++){
        sum += numstring.charAt(j) - '0';
    }
    System.out.print(sum);
  }
}

possible duplicate of [StackOverflowError computing factorial of a BigInteger?](http://stackoverflow.com/questions/8992437/stackoverflowerror-computing-factorial-of-a-biginteger) — Tavo, Aug 21 '15 at 14:24
Start by printing out `num` after `num = num * i;`, that will give you some insight to why your code does not work. — Tawcharowsky, Aug 21 '15 at 14:26
Now is the time to learn what the number of bits mean for the various datatypes :) — Thorbjørn Ravn Andersen, Aug 21 '15 at 14:38
@Tavo I disagree that this is a duplicate of the question to which you link. The problem in that question relates to recursion and in this question recursion is not involved. — Bobulous, Aug 21 '15 at 14:45
http://forum.projecteuler.net/viewtopic.php?f=5&t=3078#p32985 "**We strongly disapprove of posting solutions that are accesible to the general public. If you feel like having your solutions somewhere else, please use some password only known to you, or use some encryption. The reason should be obvious: members coming after you are supposed to solve the problems themselves as you have done.**" Posting answers outside of Project Euler defeats the purpose of the service offered there, please be a little more respectful to these communities. — Blake Yarbrough, Aug 21 '15 at 14:49

score 4 · Answer 1 · edited May 23 '17 at 11:54

Every time you multiply by 2, you add a 0 to the low bits of binary representation of the number.

According to the JLS §15.17.1:

If an integer multiplication overflows, then the result is the low-order bits of the mathematical product as represented in some sufficiently large two's-complement format. As a result, if overflow occurs, then the sign of the result may not be the same as the sign of the mathematical product of the two operand values.

Here's some code to demonstrate this point. As you can see, the number of 0 at the end of the number slowly increases; soon as we get to 32, the low order bits become all 0. See: Why does this multiplication integer overflow result in zero?

public class Problem20 {
  public static void main(String[] args) {
    int num = 100;

    for (int i = 1; i < 33; i++) {
      num = num * i;
      System.out.println(i + "\t" + Integer.toBinaryString(num));
    }
  }
}

Output:

1   1100100
2   11001000
3   1001011000
4   100101100000
5   10111011100000
6   10001100101000000
7   1111011000011000000
8   1111011000011000000000
9   10001010011011011000000000
10  10101101000010001110000000000
11  11101101111011000011010000000000
12  100111000100100111000000000000
13  11111011111011111011000000000000
14  11000111000110111010000000000000
15  10101010100111100110000000000000
16  10101001111001100000000000000000
17  1001000010001100000000000000000
18  10100111011000000000000000000
19  10001101100001000000000000000000
20  1110010100000000000000000000
21  101100100100000000000000000000
22  11010100011000000000000000000000
23  10100101000000000000000000000
24  11101111000000000000000000000000
25  1010111000000000000000000000000
26  11010110000000000000000000000000
27  10010010000000000000000000000000
28  11111000000000000000000000000000
29  11000000000000000000000000000
30  11010000000000000000000000000000
31  110000000000000000000000000000
32  0

You can solve this problem by using BigInteger instead of int, e.g.

import java.math.BigInteger;

public class Problem20 {
  public static void main(String[] args) {
    BigInteger num = BigInteger.valueOf(100);

    for (int i = 1; i < 100; i++) {
      num = num.multiply(BigInteger.valueOf(i));
      System.out.println(num);
    }
  }
}

score 2 · Answer 2 · answered Aug 21 '15 at 14:31

Alright.

1! = 1
2! = 2
3! = 6
4! = 24
.
.
.
10! = 3628800
.
.
100! = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

Do you think this fits in any of those data-types?

What happens once a number crosses the limit? It overflows. And hence you get a wrong answer.

So what do I do?

Use BigInteger.

Why does my factorial program print 0?

2 Answers2