GATE CS 2014 Set 2 Q11 — Programming in C

To compute $^nC_3 = \frac{n(n-1)(n-2)}{6}$ for a large unsigned integer $n$, we must avoid two major issues in integer arithmetic:

1. Integer Overflow: Computing the product $n \times (n-1) \times (n-2)$ first can easily exceed the maximum limit of an unsigned int.
2. Truncation Error: Performing integer division when the numerator is not perfectly divisible by the denominator results in a loss of fractional parts.

Let's analyze each option:

• Option A: p = n * (n-1) * (n-2) / 6;
  The product $n(n-1)(n-2)$ is evaluated first. For large $n$, this will overflow the unsigned int range before the division by 6 is performed, leading to an incorrect result.
• Option B: p = n * (n-1) / 2 * (n-2) / 3;
  
  • Out of two consecutive integers $n$ and $(n-1)$, one must be even. Thus, $n(n-1)$ is always divisible by $2$. The division n * (n-1) / 2 is exact and does not lose any fractional part.
  • This intermediate value is $^nC_2$. Since $^nC_3 = \frac{^nC_2 \times (n-2)}{3}$ is mathematically an integer, the product $^nC_2 \times (n-2)$ is guaranteed to be divisible by $3$. Thus, the final division by $3$ is also exact.
  • Dividing by $2$ early significantly reduces the size of the intermediate product, making it highly resilient to overflow.
• Option C: p = n * (n-1) / 3 * (n-2) / 2;
  The product $n(n-1)$ is not always divisible by $3$ (e.g., if $n = 5$, $5 \times 4 = 20$, which is not divisible by $3$). Integer division n * (n-1) / 3 will truncate the remainder, resulting in an incorrect final value.
• Option D: p = n * (n-1) * (n-2) / 6.0;
  The numerator $n * (n-1) * (n-2)$ is evaluated using unsigned int arithmetic before being divided by the double constant 6.0. Thus, it suffers from the exact same overflow issue as Option A.

Therefore, Option B is the most robust and correct statement.