Log In
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?

  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;$
in Programming
edited by

4 Answers

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

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?

Can’t we prove this using below method,

nCr =n! /(n-r)! r!


nC1 =n
nC2 = n*(n-1)/2
nC3 = n*(n-1)/2*(n-2)/3

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.
n*(n-1)/ 2*(n-2), gives a number which is a multiple of 3??
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


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

No, it will be cube root because you are multiplying 3 integers not 2.

Related questions

29 votes
5 answers
Consider the C function given below. int f(int j) { static int i = 50; int k; if (i == j) { printf("something"); k = f(i); return 0; } else return 0; } Which one of the following is TRUE? The function returns $0$ for all values of $j$. The function prints ... of $j$. The function returns $0$ when $j = 50$. The function will exhaust the runtime stack or run into an infinite loop when $j = 50$.
asked Sep 28, 2014 in Programming jothee 4.2k views
39 votes
3 answers
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)$ will return $q$:_____.
asked Sep 28, 2014 in Programming jothee 6.6k views
71 votes
9 answers
For a C program accessing $\mathbf{X[i] [j] [k]}$, the following intermediate code is generated by a compiler. Assume that the size of an integer is $32$ bits and the size of a character is $8$ bits. t0 = i ∗ 1024 t1 = j ∗ 32 t2 = k ∗ 4 t3 = t1 + t0 t4 = t3 + t2 t5 = X[t4] ... $\mathbf{X}$ is declared as "char $\mathbf{X[4] [32] [8]}$ . $\mathbf{X}$ is declared as "char $\mathbf{X[32] [16] [2]}$ .
asked Sep 28, 2014 in Compiler Design jothee 11.9k views
55 votes
3 answers
Consider the main memory system that consists of $8$ memory modules attached to the system bus, which is one word wide. When a write request is made, the bus is occupied for $100$ nanoseconds (ns) by the data, address, and control signals. During the same $100$ ns, ... be on the bus at any time. The maximum number of stores (of one word each) that can be initiated in $1$ millisecond is ________
asked Sep 28, 2014 in Operating System jothee 11.5k views