I was looking into this 369: Combinations problem where very very large integer is being used for you have to get combinations C by solving n choose m, where largest n = m= 100. Approximately, we know that the largest no. of digits occur at around 100 choose 50. However, there's a tricky line that says that the value of C will not cross 32-bit long int! That means that such input cases will not exist which will cause a final overflow of long int. However, there is no saying that the intermediate numbers that you use, rather, the numerators and denominators as below won't cross 32-bit. The formula is already given to be:
C = n! / ( (n-m)! x m!)
At first instance it seems scary, but if you recall that each factorial starts with 1 x 2 x 3 x... x n or m or (n-m), then we can put together simple high school math and see that the common numbers from numerator and denominator get cancelled out! (By the way, that last one isn't out factorial. :-P)
If we write the above another way,
C = (n! / m!) / (n-m)!
Clearly, all terms from n! upto m! can just get cancelled out right away. Now, lets see them separately as numerators and denominator so:
num = n! /m! and den = (n-m)!
Taking an example of n = 10, m = 6:
num = (1x2x3x4x5x6x7x8x9x10) / (1x2x3x4x5x6)
= 7x8x9x10
= (m+1) x (m+2) x ... x n
den = 1x2x3x4
= (n-m)!
As we can see, we don't need to deduce both multiplications as of yet, since there are many more reductions in numerator to happen. Moreover, for small nos, there won't be any overflow, but for larger ones there will be. That is, instead of multiplying first, we could see if we can divide individual terms first. Here come the vectors to hold individual terms.
Now, we could use two vectors of long long int for num and den. Then, although its a lot more times than perhaps needed, the following reduction helps:
Before:
num = 51x52x53x54x55x56x57x58x59x60x61x62x63x64x65x66x67x68x69x70x71x72x73x74x75x76x77x78x79x80x81x82x83x84x85x86x87x88x89x90x91x92x93x94x95x96x97x98x99x100
den = 2x3x4x5x6x7x8x9x10x11x12x13x14x15x16x17x18x19x20x21x22x23x24x25x26x27x28x29x30x31x32x33x34x35x36x37x38x39x40x41x42x43x44x45x46x47x48x49x50
After:
num = 2x53x3x2x59x6x61x2x9x8x65x3x67x2x3x2x71x6x73x2x5x2x77x3x79x5x3x2x83
x4x85x2x87x2x89x5x91x2x93x2x95x4x97x2x3x5
den: 25x28x30x32x36x39x40x42x45x48x50
Possibly the numerator spills over a long long int, but such a test case won't exist in the input. You get the idea here that the numerator has terms that divides the denominator, those can go too if you check for the divisibility other way round.
Cheers!
C = n! / ( (n-m)! x m!)
At first instance it seems scary, but if you recall that each factorial starts with 1 x 2 x 3 x... x n or m or (n-m), then we can put together simple high school math and see that the common numbers from numerator and denominator get cancelled out! (By the way, that last one isn't out factorial. :-P)
If we write the above another way,
C = (n! / m!) / (n-m)!
Clearly, all terms from n! upto m! can just get cancelled out right away. Now, lets see them separately as numerators and denominator so:
num = n! /m! and den = (n-m)!
Taking an example of n = 10, m = 6:
num = (1x2x3x4x5x6x7x8x9x10) / (1x2x3x4x5x6)
= 7x8x9x10
= (m+1) x (m+2) x ... x n
den = 1x2x3x4
= (n-m)!
As we can see, we don't need to deduce both multiplications as of yet, since there are many more reductions in numerator to happen. Moreover, for small nos, there won't be any overflow, but for larger ones there will be. That is, instead of multiplying first, we could see if we can divide individual terms first. Here come the vectors to hold individual terms.
Now, we could use two vectors of long long int for num and den. Then, although its a lot more times than perhaps needed, the following reduction helps:
- For each term i of num
- For each term j of den
- If i is divisible by j
- replace i from num by i/j
- erase j from den
- if i is 1, erase i
Before:
num = 51x52x53x54x55x56x57x58x59x60x61x62x63x64x65x66x67x68x69x70x71x72x73x74x75x76x77x78x79x80x81x82x83x84x85x86x87x88x89x90x91x92x93x94x95x96x97x98x99x100
den = 2x3x4x5x6x7x8x9x10x11x12x13x14x15x16x17x18x19x20x21x22x23x24x25x26x27x28x29x30x31x32x33x34x35x36x37x38x39x40x41x42x43x44x45x46x47x48x49x50
After:
num = 2x53x3x2x59x6x61x2x9x8x65x3x67x2x3x2x71x6x73x2x5x2x77x3x79x5x3x2x83
x4x85x2x87x2x89x5x91x2x93x2x95x4x97x2x3x5
den: 25x28x30x32x36x39x40x42x45x48x50
Possibly the numerator spills over a long long int, but such a test case won't exist in the input. You get the idea here that the numerator has terms that divides the denominator, those can go too if you check for the divisibility other way round.
Cheers!
No comments:
Post a Comment