89 votes

Suppose $n$ and $p$ are unsigned int variables in a C program. We wish to set p to $^nC_3$. If $n$ is large, which one of the following statements is most likely to set p correctly?

- $p = n * (n-1) * (n-2) / 6;$
- $p = n * (n-1) / 2 * (n-2) / 3;$
- $p = n * (n-1) / 3 * (n-2) / 2;$
- $p = n * (n-1) * (n-2) / 6.0;$

186 votes

Best answer

**Answer is (B).**

In c, $*$ and $/$ have the same precedence and are left associative.

Evaluation of $n*(n-1)*(n-2)$ might exceed the unsigned int range.

So, **(A)** and** (D) **are eliminated.

$n*(n-1)$ is always divisible by $2$.(Gives an integer value). Where as it is not always divisible by $3$.(You don't always get an integer..truncation possible, less accuracy)

**(C) **eliminated.

In option **(B)**

$n*(n-1)/2$ gives an integer value.

This integer value multiplied by $(n-2)$ again gives an integer value.

Which when divided by $3$ gives an integer value(Sets $p$ correctly).

Reason : $n*(n-1)*(n-2)$ is the multiplication of $3$ consecutive numbers. which is divisible by $2$ as well as $3$.

Hence, $( n*(n-1)/2*(n-2) )$ is divisible by $3$.

0

@ Arjun sir , please give more clearification of B and C option both seem same . ( n-2/3 again it can give non integer value if we take n =7 and now in this case how can we eleminate c )

4 votes

As n is large, the product n*(n-1)*(n-2) will go out of the range(overflow) and it will return a value different from what is expected. So we consider a shorter product n*(n-1). n*(n-1) is always an even number. So the subexpression "n * (n-1) / 2 " in option B would always produce an integer, which means no precision loss in this subexpression. And when we consider `n*(n-1)/2*(n-2)`, it will always give a number which is a multiple of 3. So dividing it with 3 won't have any loss.

3 votes

n & p are unsigned int variable.

From the options n*(n-1)*(n-2) will go out of range. So eliminate A & D.

n*(n-1) is always an even number. So subexpression n(n-1)/2 also an even number.

n*(n-1)/ 2*(n-2), gives a number which is a multiple of 3. So dividing with 3 will not have any loss. Hence B is option.

From the options n*(n-1)*(n-2) will go out of range. So eliminate A & D.

n*(n-1) is always an even number. So subexpression n(n-1)/2 also an even number.

n*(n-1)/ 2*(n-2), gives a number which is a multiple of 3. So dividing with 3 will not have any loss. Hence B is option.

0 votes

Eliminate D due to floating-point to integer conversion.

We know that multiplying consecutive numbers $2\lambda-1 * 2\lambda = 4\lambda^2 - 2\lambda = 2(2\lambda^2 - 1) = 2\sigma$, This is always even, Thus it is safe to divide this safe by 2. Eliminate C, because this will cause rounding error.

A and B are left as viable alternatives mathematically.

Since multiplication is used, it is better to do this 2 at a time than all three together. Because when you do 3 multiplications together all values greater than $\sqrt[3](2^{32})$ will lead to overflow. Eliminating A.

So we are left with **B**

0

@siddharths067 in the last line it should be values greater than **$\sqrt[2]{2^{32}}$** as it is the upper limit for unsigned int right? Someone correct me if I am wrong.