Найти количество возможных триплетов (включая дубликаты) элементов массива в линейном времени?

Question

Я попытался с помощью функции NCM, чтобы найти все комбинации, но и для больших чисел он не

int fact(int num) 
{ 
    if (num == 1 || num == 0) 
     return 1; 
    return num * fact(num-1); 
} 

int nCm(int num, int base) 
{ 
    int result; 
    return result = fact(num)/(fact(num - base)*fact(base)); 
} 

где base = 3 и Num может быть что угодно, так что при больших пит это не удается. Я не могу использовать библиотеку BigInteger так, пожалуйста, помогите

Answer 1

Если вы считаете, что деление на мгновение, вы увидите, что (n-b)! термин является общим для обоих числитель и знаменатель (т.е. они взаимно сокращаются).

Вам просто нужно думать о n! как:

n * (n-1) * (n-2) * ... * (n-b+1) * (n-b)! 

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