Почему я получаю «Ваш код не был выполнен в установленные сроки» в рейтинге хакера?

Question

static BigInteger handshake(int n) {

    BigInteger fact = BigInteger.ONE;
    int res = n-1;

    for(int i= res ; i>0 ;i--)
    {  
       fact=fact.multiply(BigInteger.valueOf(i));
    }

    if(res==0){return BigInteger.ZERO;}
    else{
       return fact;
    }
}

Это функция факториала, которую я создал. Я использовал класс BigInteger, чтобы он мог хранить более крупные целые числа.

Answer 1

Не думаю, что есть способ ускорить вычисление факториала на порядок (хотя в комментариях есть несколько интересных идей). Хорошая новость заключается в том, что, вероятно, проблема здесь не в этом - ваш алгоритм неверен.

n! - это количество способов, которыми вы можете отсортировать n элементов, но проблема здесь намного проще. Учитывая n человек, каждый пожимает руки всем остальным, то есть n-1 другим людям. Затем мы делим это пополам, так как Алиса, пожимая руку Бобу, точно так же, как Боб, пожимая руку Алисе. Итак, короче говоря, вам не нужно находить факториал n. И поскольку n * (n-1)/2 находится в пределах long для данного диапазона ввода, вам также не нужно возиться с BigInteger s:

private static long handshake(long n) {
    return n * (n - 1L) / 2L;
}