Contando los ceros finales de los números resultantes del factorial

Question

Estoy tratando de contar los ceros finales de los números que son resultado de los factoriales (lo que significa que los números son bastante grandes). El código siguiente toma un número, calcule el factorial del número y cuente los ceros finales. Sin embargo, cuando el número es aproximadamente tan grande como 25 !, los numZeros no funcionan.

public static void main(String[] args) { 
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
    double fact; 
    int answer; 

    try { 
     int number = Integer.parseInt(br.readLine()); 
     fact = factorial(number); 
     answer = numZeros(fact); 
    } 
    catch (NumberFormatException e) { 
     e.printStackTrace(); 
    } catch (IOException e) { 
     e.printStackTrace(); 
    } 
} 

public static double factorial (int num) { 
    double total = 1; 
    for (int i = 1; i <= num; i++) { 
     total *= i; 
    } 
    return total; 
} 

public static int numZeros (double num) { 
    int count = 0; 
    int last = 0; 

    while (last == 0) { 
     last = (int) (num % 10); 
     num = num/10; 
     count++; 
    } 

    return count-1; 
} 

No me preocupa la eficiencia de este código, y sé que hay varias maneras de hacer que la eficiencia de este código MEJOR. Lo que estoy tratando de averiguar es por qué el conteo de ceros finales de números que son mayores que 25! no está trabajando.

¿Alguna idea?

Answer 1

Su tarea no consiste en calcular el factorial pero el número de ceros. Una buena solución utiliza la fórmula de http://en.wikipedia.org/wiki/Trailing_zeros (que se puede tratar de demostrar)

def zeroes(n): 
    i = 1 
    result = 0 
    while n >= i: 
     i *= 5 
     result += n/i # (taking floor, just like Python or Java does) 
    return result 

espera que usted pueda traducir esto a Java. Esto simplemente calcula [n/5] + [n/25] + [n/125] + [n/625] + ... y se detiene cuando el divisor es mayor que n.

NO utilice BigIntegers. Este es un bozosort. Tales soluciones requieren segundos de tiempo para grandes cantidades.

Answer 2

Solo necesita saber cuántos 2 y 5 hay en el producto. Si está contando los ceros finales, entonces realmente está contando "¿Cuántas veces diez divide este número?". si representas a n! como q * (2^a) * (5^b) donde q no es divisible entre 2 o 5. Entonces, simplemente tomando el mínimo de a y b en la segunda expresión, se obtendrá la cantidad de veces que 10 divide el número. En realidad, hacer la multiplicación es excesivo.

Editar: Contando los dos es también exagerado, por lo que realmente solo necesitas los cincos.

Y por alguna pitón, creo que esto debería funcionar:

def countFives(n): 
    fives = 0 
    m = 5 
    while m <= n: 
     fives = fives + (n/m) 
     m = m*5 
    return fives 

Answer 3

Se puede utilizar un DecimalFormat para dar formato a los grandes números. Si formatea su número de esta manera obtiene el número en scientific notation, entonces cada número será como 1.4567E7, esto hará su trabajo mucho más fácil. Porque el número después de E: el número de caracteres detrás de. son el número de ceros finales, creo.

No sé si este es el patrón exacto necesario. Se puede ver cómo se forman los patrones here

DecimalFormat formater = new DecimalFormat("0.###E0"); 

Answer 4

El tipo de doble precisión ha limitado, por lo que si los números que está trabajando demasiado grandes el doble habrá sólo una aproximación. Para solucionar este problema, puede usar algo como BigInteger para que funcione para enteros arbitrariamente grandes.

Answer 5

¡El doble de Java supera un poco más de 9 * 10^18 donde tiene 25! es 1.5 * 10^25. Si desea poder tener factoriales tan altos es posible que desee utilizar BigInteger (similar a BigDecimal pero no hace decimales).

Answer 6

Escribí esto muy rápido, creo que resuelve su problema con precisión. Utilicé la clase BigInteger para evitar el lanzamiento de doble a entero, que podría causarle problemas. Lo probé en varios números grandes de más de 25, como 101, que arrojaron con precisión 24 ceros.

La idea detrás del método es que si toma 25! entonces el primer cálculo es 25 * 24 = 600, por lo que puede eliminar dos ceros inmediatamente y luego hacer 6 * 23 = 138. Por lo tanto, calcula el factorial eliminando ceros a medida que avanza.

public static int count(int number) { 
    final BigInteger zero = new BigInteger("0"); 
    final BigInteger ten = new BigInteger("10"); 
    int zeroCount = 0; 
    BigInteger mult = new BigInteger("1"); 
    while (number > 0) { 
     mult = mult.multiply(new BigInteger(Integer.toString(number))); 
     while (mult.mod(ten).compareTo(zero) == 0){ 
      mult = mult.divide(ten); 
      zeroCount += 1; 
     } 
     number -= 1; 
    } 
    return zeroCount; 
} 

Dado que usted ha dicho que no se preocupan por el tiempo de ejecución en absoluto (no es que mi primera fue particularmente eficiente, sólo un poco más) éste sólo lo hace el factorial y luego cuenta los ceros, por lo que es cenceptually más sencillo :

public static BigInteger factorial(int number) { 
    BigInteger ans = new BigInteger("1"); 
    while (number > 0) { 
     ans = ans.multiply(new BigInteger(Integer.toString(number))); 
     number -= 1; 
    } 
    return ans; 
} 

public static int countZeros(int number) { 
    final BigInteger zero = new BigInteger("0"); 
    final BigInteger ten = new BigInteger("10"); 
    BigInteger fact = factorial(number); 
    int zeroCount = 0; 
    while (fact.mod(ten).compareTo(zero) == 0){ 
     fact = fact.divide(ten); 
     zeroCount += 1; 
    } 
} 

Answer 7

Mis 2 centavos: evite trabajar con doble ya que son propensos a errores. Un mejor tipo de datos en este caso es BigInteger, y aquí hay un pequeño método que le ayudará a:

public class CountTrailingZeroes { 

    public int countTrailingZeroes(double number) { 
     return countTrailingZeroes(String.format("%.0f", number)); 
    } 

    public int countTrailingZeroes(String number) { 
     int c = 0; 
     int i = number.length() - 1; 

     while (number.charAt(i) == '0') { 
      i--; 
      c++; 
     } 

     return c; 

    } 

    @Test 
    public void $128() { 
     assertEquals(0, countTrailingZeroes("128")); 
    } 

    @Test 
    public void $120() { 
     assertEquals(1, countTrailingZeroes("120")); 
    } 

    @Test 
    public void $1200() { 
     assertEquals(2, countTrailingZeroes("1200")); 
    } 

    @Test 
    public void $12000() { 
     assertEquals(3, countTrailingZeroes("12000")); 
    } 

    @Test 
    public void $120000() { 
     assertEquals(4, countTrailingZeroes("120000")); 
    } 

    @Test 
    public void $102350000() { 
     assertEquals(4, countTrailingZeroes("102350000")); 
    } 

    @Test 
    public void $1023500000() { 
     assertEquals(5, countTrailingZeroes(1023500000.0)); 
    } 
} 

Answer 8

Esto es cómo lo hice, pero con grandes> 25 factorial de la larga capacidad no es suficiente y se debe utilizar la clase BigInteger, con la bruja todavía no estoy familiarizado :)

public static void main(String[] args) { 
    // TODO Auto-generated method stub 
    Scanner in = new Scanner(System.in); 
    System.out.print("Please enter a number : "); 
    long number = in.nextLong(); 
    long numFactorial = 1; 

    for(long i = 1; i <= number; i++) { 
     numFactorial *= i; 
    } 
    long result = 0; 
    int divider = 5; 
    for(divider =5; (numFactorial % divider) == 0; divider*=5) { 
     result += 1; 
    } 

    System.out.println("Factorial of n is: " + numFactorial); 
    System.out.println("The number contains " + result + " zeroes at its end."); 

    in.close(); 

} 

} 

Answer 9

La mejor con logarítmica complejidad del tiempo es la siguiente:

public int trailingZeroes(int n) { 
    if (n < 0) 
     return -1; 

    int count = 0; 
    for (long i = 5; n/i >= 1; i *= 5) { 
     count += n/i; 
    } 

    return count; 
} 

descaradamente copiado de http://www.programcreek.com/2014/04/leetcode-factorial-trailing-zeroes-java/

Answer 10

que tenía el mismo problema a resolver en Javascript, y yo s lo olvidé como:

var number = 1000010000; 
var str = (number + '').split(''); //convert to string 
var i = str.length - 1; // start from the right side of the array 
var count = 0; //var where to leave result 
for (;i>0 && str[i] === '0';i--){ 
    count++; 
} 
console.log(count) // console shows 4 

Esta solución le da el número de ceros finales.

var number = 1000010000; 
 
var str = (number + '').split(''); //convert to string 
 
var i = str.length - 1; // start from the right side of the \t array 
 
var count = 0; //var where to leave result 
 
for (;i>0 && str[i] === '0';i--){ 
 
\t count++; 
 
} 
 
console.log(count)