Why is Project Euler say I am getting No. 20 wrong?

Question

Here is the problem I am trying to solve: Euler 20.

n! means n ⨉ (n - 1) ⨉ ... ⨉ 3 ⨉ 2 ⨉ 1

For example, 10! = 10 ⨉ 9 ⨉ ... ⨉ 3 ⨉ 2 ⨉ 1 = 3628800, and the sum of the digits in the number 10! is 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27.

Find the sum of the digits in the number 100!

I have tried this:

y = 1  #The actual number
sum = 0 #The sum of its digits.

def factorial(x): #Calculates the number using a recursive factorial algorithm
    global y
    y = y*x
    if x > 1:
        factorial(x-1)
    else:
        return 0

factorial(100) #Calculate 100! and the function will put it in y.

def count(): #Calculates the sum.
    global y, sum
    while y > 0:
        currentDigit = int(y) % 10 #Find the remainder of the number gives the very last digit
        sum = sum + currentDigit #Add that to the total sum.
        y = int(y) / 10 #Divide y by 10 knocking of the 1s-digit place and putting the 10s digit in its place.
    return sum #return the sum.

print(count()) #print the count.

If I do factorial(10) instead of 100 I get 27 which is what the problem says I should get, but I get 675 for factorial(100) which the program says is wrong. What did I do wrong? I am not that familiar with Python, sorry if I made a stupid error.

Answer 1

The problem lies in your implementation of count, specifically the line:

    y = int(y) / 10

Since Python 3, / is true division. In Python 2.2 and later, you can get Python 3's division behavior with from __future__ import division. After executing the above line, y is a float. Python floats on most systems only have about 15 significant decimal digits (sys.float_info.dig will give you the precision for your system; note that there are actually 53 bits of precision, which is equal to 53 / log₂(10) ≈ 15.955). Any decimal digit that count extracts after those significant ones is the result of rounding error and is a consequence of converting a base-2 float into base 10. Over a certain length, the middle digits won't contribute to the sum calculated by count.

[count(int('8' * 17 + str(k) + '0')) for k in range(1, 10)]
# [130, 130, 130, 130, 130, 130, 130, 130, 130]
import random
[count(int('8' * 17 + ('%05d' % random.randint(1,99999)) + '0')) for k in range(1, 10)]
# [146, 146, 146, 146, 146, 146, 146, 146, 146]

The solution is to use // for integer division, at which point you can also remove the int conversions. While you're at it, you might as well make y a parameter to count, and make sum local. Otherwise, your global sum variable will hide the built-in sum function.

As for doing away with the global y in factorial, it's quite easy to pass an extra argument:

def factorial(x, p=1):
    p *= x
    if x > 1:
        return factorial(x-1, p)
    else:
        return p

This has the advantage of being tail-recursive. The standard python interpreter doesn't implement the tail call optimization, but it can be done with a decorator. Apply such a decorator to factorial and the result is a function that won't cause a stack overflow. This technique of passing an accumulation can be used for many other functions to create a tail-recursive function.

Alternatively, write an iterative version, which is a little more pythonic.

Answer 2

Here's an easy way to re-write your factorial() function so that it no longer relies on global variables:

>>> def fac(x):
...   if x > 1:
...     return x * fac(x-1)
...   else:
...     return 1
... 
>>> fac(10)
3628800
>>> fac(100)
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000L

It relies upon returning a value and calling itself recursively to perform the calculation. Granted, to calculate 100! means the call-chain will be 100 levels deep, but for the clarity in this function, I think the tradeoff is well worth it. (There might be more robust ways to write this function -- handle negatives or non-integers better, for example.)

There's a few ways you can find the sum of the digits -- consider approaches that look at either the large number as a single string, iterate through all characters, and sum up the integer values of the digits and approaches that treat the number as a number, find the value of the lowest digit in its decimal representation, and removes that lowest digit once you've accounted for it. Both approaches work.

As for the actual error in your summer, I hope this is educational:

$ python3.2 -c "print (755 / 10)"
75.5
$ python2.7 -c "print (755 / 10)"
75

Answer 3

Find the sum of the digits in the number 100!

def sumFactorial(n):
    factorial=str(reduce(lambda x,y:x*y, range(n,0,-1))) 
    return sum(int(x) for x in factorial)

>>> sumFactorial(10)
27
>>> sumFactorial(100)
648
>>> 

Answer 4

//In c++
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int main()
{
    int a[200];
    int carry=0,temp,m=1,k=0;
    int n;
    cin>>n;
    a[0]=1;
    for(int i=1;i<=n;i++)
    {
        k=0;
        for(int j=0;j<m;j++)
        {
            temp=a[j]*i+carry;  
            a[j]=temp%10;
            carry=temp/10;

        }
        while(carry!=0)
        a[m++]=carry%10,carry/=10;

    }
    long long ans=0;
    for(int i=m-1;i>=0;i--)
    {
    ans+=a[i];
    }
    cout<<endl;
    cout<<ans<<endl;
}
1.Array a[200] is used to store the digits of factorial.
2.Outer loop run from 1..100
3.varible m indicates no of digits in array or factorial
4.now lets take a example
  take a simple multiplication
  25 x 12
-------------
   5 0
 2 5
-------------
 3 0 0
300- value stores in temp;
by taking modulo 10 we can get the last digit it is placed array
300/10 becomes carry.

Answer 5

I see that you are using a lot of global variables.

First things first:

I think instead of using global y, you can use y in the function and return the value return y.

Also instead of framing a new function yourself, I think you could have used built-in functions. Remember using the inbuilt functions is more efficient than the ones which we create. I am not saying that the function which you have created is not efficient(In fact the factorial function you have created has a very efficient implementation), but sometimes the efficiency of the built in functions is more when compared to the ones we create.

Instead of writing a new factorial function you could have imported the factorial function from the math module.

>>> from math import factorial

To break your number into digits you can do as follows:

>>> a = list(str(factorial(100)))

As you can see we are converting the number to string, breaking it, and thus the list has digits in the form of string. So you should convert it back to int again. To do that:

>>> a = [int(x) for x in a]

I have used list comprehension in above code.

Finally use inbuilt sum function to get the solution.

>>> a = sum(a)