Блог

Я пытался решить проблему 20 в Project Euler:

n! означает n (n 1) … 3 * 2 * 1 Например, 10! = 10 * 9 … 3 * 2 * 1 = 3628800, а сумма цифр в числе 10! это 3 6 2 8 8 0 0 = 27. Найдите сумму цифр в числе 100!

Это то, что я придумал до сих пор. Я уже получил правильный ответ (который был 648) с этим кодом, но я получил немного OC, потому что мой код представляет собой бесконечный цикл. После того, как результат стал 0 внутри цикла while, он просто не остановится. Кто-нибудь может помочь мне исправить это?

 public static BigInteger problem20(int max){
    BigInteger sum = BigInteger.valueOf(0);
    BigInteger result = BigInteger.valueOf(1);
    BigInteger currentNum = BigInteger.valueOf(0);

    for(long i = 1; i<=max; i  ){
        result  = result.multiply(BigInteger.valueOf(i));
        //System.out.println(result);
    }

    while (!result.equals(0)) {
        sum = sum.add(result.mod(BigInteger.valueOf(10)));
        result = result.divide(BigInteger.valueOf(10));
        System.out.println(sum   " "  result);
    }
    return sum;
}
  

В этом проблема:

 while (!result.equals(0))
  

result это a BigInteger , которое никогда не будет равно an Integer . Попробуйте использовать

 while (!result.equals(BigInteger.ZERO))
  

Другая возможность — использовать while (fact.compareTo(BigInteger.ZERO) > 0) .

Я рекомендую вам использовать BigInteger.ZERO , BigInteger.ONE и BigInteger.TEN где это возможно.

Пример:

 import java.math.BigInteger;

public class P20 {

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

    private static long getSum(int n) {
        BigInteger fact = BigInteger.ONE;
        for (int i = 2; i <= n; i  ) {
            fact = fact.multiply(BigInteger.valueOf(i));
        }
        long sum = 0;
        while (fact.compareTo(BigInteger.ZERO) > 0) {
            sum  = fact.mod(BigInteger.TEN).longValue();
            fact = fact.divide(BigInteger.TEN);
        }
        return sum;
    }

}
  

Это занимает 4 мс.

Это можно улучшить, используя следующее наблюдение:

• на сумму не влияют нули => вам не нужно умножать на 10 и 100, а вместо 20, 30, … достаточно использовать 2, 3, … . Конечно, вы можете обобщить это правило, используя следующий факт 5*k * 2*j , который делится на 10 .

Пожалуйста, измените свой код на :

     while (!result.equals(BigInteger.valueOf(0))) {
        sum = sum.add(result.mod(BigInteger.valueOf(10)));
        result = result.divide(BigInteger.valueOf(10));
        System.out.println(sum   " "  result);
    }
  

Вот еще один способ сделать то же самое.В этом случае сложность вычисления суммы равна O (1).

 import java.math.BigInteger;
import java.util.ArrayList;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Main{
    public static void main(String[] args){
BigInteger b = BigInteger.valueOf(1);
        for(int i=2;i<=5;i  ){
            b = b.multiply(BigInteger.valueOf(i));
        }
        //System.out.println(b);
  

вычисление суммы ниже

 final BigInteger NINE = BigInteger.valueOf(9);
            if(b == BigInteger.ZERO){
                System.out.println(b);
            }else if(b.mod(NINE) == BigInteger.ZERO){
                System.out.println(NINE);
            }else{
                System.out.println(b.mod(NINE));
            }

        }`
}