UVa 10219 - Find the ways !

UVa 10219 - Find the ways !

So in this problem, we are given as input (n, k) and we are required to calculate the number of digits in "n choose k".

for instance, "10 choose 5" equals "252", so we should print "3" as "252" has 3 digits.

one simple way to solve this is to calculate "n choose k" using dynamic programming and count the number of digits found. However, this will use a lot of memory and there's a simpler approach to the problem.

We all know that (n choose k) equals n!/(k! * (n - k)!)
We also know that the number of digits of "n" equals log10(n)+1
and we also know that log(a * b) = log (a) + log (b)

then the number of digits in "n choose k" = the number of digits in n!/(k! * (n - k)!) = log(n!) - log(k!) - log (n - k)!

and we know that log(n!) = log(1) + log(2) + log(3) + .... + log(n)

this gives the following solution to the problem

/*
 * Main.cpp
 *
 *  Created on: Jun 7, 2013
 *      Author: usama
 */
#include <vector>
#include <iostream>
#include <cmath>

using namespace std;

const int N = 1000000;

vector<double> cache(N+1, 0);

void digitsFact(int n)
{
    double result = 0;

    for(int i = 2; i <= n; ++i)
    {
        result += log10(i);
        cache[i] = result;
    }
}

int digitsCombin(int n, int k)
{
    int result = 1;
    result += (int)(cache[n] - cache[k] - cache [n - k]);
    return result;
}

int main(int argc, char *argv[])
{
    int n, k;
    digitsFact(N);
    while (cin >> n)
    {
        cin >> k;
        if(n == k)
            cout << "1" << endl;
        else if(n < k)
            cout << "1" << endl;
        else
        {
            if(n >= cache.size())
            {
                double result = cache[cache.size()-1];
                for(int i = cache.size(); i <= n; ++i)
                {
                    result += log10(i);
                    cache.push_back(result);
                }
            }
            cout << digitsCombin(n, k) << endl;
        }
    }
    return 0;
}