Redirected
edited by
15,398 views
130 votes
130 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?

  1. $p = n * (n-1) * (n-2) / 6;$
  2. $p = n * (n-1) / 2 * (n-2) / 3;$
  3. $p = n * (n-1) / 3 * (n-2) / 2;$
  4. $p = n * (n-1) * (n-2) / 6.0;$
edited by

4 Answers

Best answer
243 votes
243 votes

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$.

7 votes
7 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.
0 votes
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 votes
0 votes
I am confused option a

If n= 50

Then 50*49*48/6= 19,600

It's belongs to the rang (0 to 65535)

Why this option is not correct?
Answer:

Related questions

59 votes
59 votes
4 answers
2
go_editor asked Sep 28, 2014
18,121 views
Consider the following function.double f(double x){ if( abs(x*x - 3) < 0.01) return x; else return f(x/2 + 1.5/x); }Give a value $q$ (to $2$ decimals) such that $f(q)$ wi...