The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+61 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;$
asked in Programming by Veteran (115k points)
edited by | 4.1k views

2 Answers

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

answered by Active (3.7k points)
selected by
@ 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 )
suppose n=5 then
C) n(n-1)/3*(n-2)/2 =5*4/3*(n-2)/2=6 *(n-2)/2=9
@saurabh .. Thank you  . Yes i can do it simply by taking an example. How dumb i am  :p
n is large ... fine. Use long double or say float.... for p then?
nicely explained!   thank you

@saurabh rai Can you explain further how n(n-1)/3*(n-2)/2 =5*4/3*(n-2)/2=6 *(n-2)/2=9.

OK explanation
great explanation @srinath sir
Evaluation of n∗(n−1)∗(n−2) might exceed the unsigned int range.  it means if the unsigned int ranges 0 to 65535 when we are taking a large value and performing the operation it will go beyond the limit (0 to 65535)bytes that's why we are not considering these cases?? Am I right sir?
+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.
answered by Loyal (9.3k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,049 questions
53,194 answers
70,402 users