Finding sum of digits of a large factorial

Question

In the above problem, given a positive integer n it is intended to find the sum of all the digits in n!. So here is my java code for it:

public static void main (String[] args) throws java.lang.Exception
{

    Scanner sc = new Scanner(System.in);
    while(sc.hasNext())
    {
        int n = sc.nextInt();
        BigInteger b = BigInteger.valueOf(1);
        for(int i=2;i<=n;i++)
            b=b.multiply(BigInteger.valueOf(i));
        String s = b.toString();
        int sum=0;
        for(int i=0;i<s.length();i++)
            sum+=(int)(s.charAt(i)-'0');
        System.out.println(sum);
    }
}

The limits for n is n<=1000. And it works flawlessly:
INPUT

OUTPUT

But the online judge is judging this as a wrong answer. Is there any problem in using the BigInteger class?
NOTE:I want the fault in the Implementation of the BigInteger class in my program, as this solution didn't exceed the time-limit but gave a wrong answer.

@AxelH...in the first loop I find out the factorial and in the second loop I find out the sum of the digits..... — yobro97, Aug 22 '16 at 06:17
@fge.... But it is given `n` is less than or equal to 1000 right??.. — yobro97, Aug 22 '16 at 06:19
@AxelH....could you elaborate it.....I could not get you there...? — yobro97, Aug 22 '16 at 06:20
One problem is that the problem supposes an input file; you read from stdin. — fge, Aug 22 '16 at 06:23
@fge,,,its JAVA 8.....and how can we read from a file without knowing its file-name..?? — yobro97, Aug 22 '16 at 06:25
Well, the file name will have to be an argument to the program, right? — fge, Aug 22 '16 at 06:26
Forget it, it doesn't occure with "small" factorial. With bigger number toString print : **[numbers]...line is too long [...]** You should use modulo instead — AxelH, Aug 22 '16 at 06:27
@fge....the file name is not provided in the problem.....I think this will most probably not a problem here though...... — yobro97, Aug 22 '16 at 06:29
Online judges mention your answer wrong because it exceeds time limit i.e 1 second. — Shaishav Jogani, Aug 22 '16 at 06:52
I guess finding factorial and then sum up all digit is not ideal solution. You have to build algorithm that can calculate digits without finding factorial of number. — Shaishav Jogani, Aug 22 '16 at 06:54
@ShaishavJogani.....the judge shows Time-Limit-Exceeded (TLE) not wrong answer for exceeding time limits.... — yobro97, Aug 22 '16 at 08:34
Possible duplicate of [Sum of digits of a factorial](http://stackoverflow.com/questions/1469529/sum-of-digits-of-a-factorial) — Shaishav Jogani, Aug 22 '16 at 08:51

fge · Answer 1 · 2016-08-22T07:39:31.560

One of the initial conditions for your particular case is that Java 8 is used, so let's do that.

First, how to obtain the factorial for a given input number:

private static final BigInteger TWO = BigInteger.valueOf(2L);

private static BigInteger factorial(final BigInteger inputNumber)
{
    BigInteger ret = BigInteger.ONE;

    BigInteger b = TWO;

    while (b.compareTo(inputNumber) <= 0) {
        ret = ret.multiply(b);
        b = b.add(BigInteger.ONE);
    }

    return ret;
}

Then, from that number, how to obtain the number of digits? We use base 10, we can therefore use the integer division and modulo operator:

private static int digitSum(final BigInteger someInteger)
{
    int ret = 0;
    BigInteger b = someInteger;
    BigInteger[] modResult;

    while (b.compareTo(BigInteger.ZERO) > 0) {
        modResult = b.divideAndRemainter(BigInteger.TEN);
        ret += modResult[1].intValueExact();
        b = modResult[0];
    }

    return ret;
}

Now, plugging it in into a main program; you are supposed to read from a file, where inputs from that file are integers, one per line:

public final class FactDigitSum
{

    // supposes that the two methods above are defined in this class

    private static void printDigitSum(final BigInteger inputNumber)
    {
        final BigInteger factorial = factorial(inputNumber);
        System.out.println(digitSum(factorial));
    }

    // The main program
    public static void main(final String... args)
        throws IOException
    {
        if (args.length == 0)
            throw new IllegalArgumentException("No file as argument");

        final Path path = Paths.get(args[0]);

        try (
            final Stream<String> stream = Files.lines(path);
        ) {
            stream.map(BigInteger::new).forEach(FactDigitSum::printDigitSum);
        }
    }
}

Not really sure that 1000! will be stored in a integer. Something like 14! would not be stored I believe. — AxelH, Aug 22 '16 at 06:49
Umm, there is an invalid assertion there. While the final sum of the digits is guaranteed to fit in a Java int, the result of the factorial function is most definitely NOT going to. The max input value of "n" is 1000. The value of 1000! has 2568 digits which is MUCH larger than Java's Integer.MAX_VALUE. It actually won't even fit in a double. A BigInteger is required for the factorial result. — Aaron Davis, Aug 22 '16 at 06:50

Rudy Velthuis · Answer 2 · 2016-08-23T14:29:39.867

Don't use the string. Calculate the value directly from the BigInteger.

This should give you the value. I'll leave I/O to you:

public class BigIntFacSum
{
    private static int bigFacSum(final int n)
    {
        int sum = 0;
        BigInteger fac = BigInteger.valueOf(2);
        BigInteger num = BigInteger.valueOf(3);

        for (int i = 3; i <= n; i++)
        {
            fac = fac.multiply(num);
            num = num.add(BigInteger.ONE);
        }

        while (fac.compareTo(BigInteger.ZERO) > 0)
        {
             BigInteger[] quotRem = fac.divideAndRemainder(BigInteger.TEN);
             fac = quotRem[0];
             sum += quotRem[1].intValue();
        }
        return sum;
    }

    public static void main(String[] args)
    {
        System.out.println(bigFacSum(1000));
    }
}

This is pretty fast in Java 7. It should be even faster in Java 8, as that uses Karatsuba and Burnikel-Ziegler optimizations for multiplication and division respectively (as far as I know, Java 7 doesn't).

For what it's worth: If the numbers get bigger, it is possible that the detour via string and then adding the digits in the string becomes faster. The naive way of using divideAndRemainder(BigInteger.TEN) in a loop does not work well for large numbers like 100000!. I tried this with my own implementation of BigInteger (in a different language), and the string detour was much faster for such huge nubmers. That is because the conversion to decimal is highly optimized with a divide-and-conquer algorithm and much faster than the naive loop. But only for relatively large numbers, i.e. well over 10000!. AFAIK, Java uses a similar algorithm, so the conversion to string should also be faster there, for similarly huge humbers.

I am not aware of a divide-and-conquer algorithm that counts the sum of the digits at the same time, although I don't see why it couldn't. The algorithm is not trivial though, and mine is not in Java.

But that only as an aside, in case you or anyone else may need this one day.

Finding sum of digits of a large factorial

2 Answers2