GATE CSE 2014 Set 2 | Question: 11

Question

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?

• A. $p = n * (n-1) * (n-2) / 6;$
• B. $p = n * (n-1) / 2 * (n-2) / 3;$
• C. $p = n * (n-1) / 3 * (n-2) / 2;$
• D. $p = n * (n-1) * (n-2) / 6.0;$

Comments

EXCELLENT QUESTION

Answer 1

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

Comments

If anyone confused between B and C, then simply run this code:

#include <stdio.h>

int main() {
    unsigned int p;
    unsigned int n=5; //5c3=10
    
    p=n*(n-1)/2*(n-2)/3; //B
    printf("%d ", p); // outputs 10(correct)
     
    p=n*(n-1)/3*(n-2)/2;//C
    printf("%d ", p); //outputs 9(wrong)

    return 0;
}

 

---

The line which makes all the difference: - 

$n*(n-1) $ is always divisible by $2$ whereas it is not always divisible by $3$

---

I get why n(n-1)/2  is completely divisible but if number is too large as given in question shouldn’t we choose to do n (n-1)/3 first . what matters here accuracy or range of the result ?

Answer 2

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.

Answer 3

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

Comments

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