GATE CSE 2014 Set 1 | Question: 42

Question

Consider the following pseudo code. What is the total number of multiplications to be performed?

D = 2    
for i = 1 to n do
    for j = i to n do
        for k = j + 1 to n do
            D = D * 3 

• A. Half of the product of the $3$ consecutive integers.
• B. One-third of the product of the $3$ consecutive integers.
• C. One-sixth of the product of the $3$ consecutive integers.
• D. None of the above.

Comments

Simplified version of the selected answer for the people like me who are below the  poverty line in Maths:

---

Thanks xD

---

I put n=3. Do simple dry run. and u will see that the multiplication runs 4 times.

now, as we chose n=3, the 3 consecutive integers' product maybe 1x2x3 or 2x3x4 or 3x4x5.

It is easy to see, (2x3x4)/6 = 4.

therefore option c is answer

---

I am thinking it to solve in another way that ------- D=2 and its first time mulitplication with 3 gaurantees that its a multiple of 6. Now we can check whether its a product of 3 consecutive integers or not but taking any value.

Will it be a correct approach?

---

Take n=8 and unroll the loops:

i=1 ; j=1 ; k= 2 to 8: MUL = 7

i=1 ; j=2 ; k=3 to 8: MUL= 6

i=1 ; j = 3; k=4 to 8: MUL= 5

i=1 ; j = 4; k=5 to 8: MUL= 4

i=1 ; j = 5; k=6 to 8: MUL= 3

i=1 ; j = 6; k=7 to 8: MUL= 2

i=1 ; j = 7; k=8 to 8: MUL= 1

i=1 ; j = 8; k=9; stops.      

MUL = 28 for i =1

Similarly, now we can do for i =2 to 8 as

i=2 ; j = 2 to 8; MUL= 6+5+4+3+2+1 = 21

i=3 ; j = 3 to 8; MUL= 5+4+3+2+1 = 15

i=4 ; j = 4 to 8; MUL= 4+3+2+1 = 10

i=5 ; j = 5 to 8; MUL= 3+2+1 = 6

i=6 ; j = 6 to 8; MUL= 2+1 = 3

i=7 ; j = 7 to 8; MUL= 1

i=8 ; j = 8 to 8; MUL= 0

So, total $MUL = 28 + 21+15+10+6+3+1 = 84$

Now, product of three consecutive integers : $(n-1)n(n+1)$

put $n=8$. we get product = 504.

$\therefore MUL = \frac{1}{6}\ ( Product\ of\ three\ consecutive\ int)$

Option (C) is answer.

 

---

The above method suggested by Sukhbir is correct until he said with n =3 we can have 1*2*3 or whatever extra he mentioned. In reality when we are doing with this question with option-putting(jugaad) we don’t know the final result it can be any 3 consecutive numbers they are talking about maybe 100*101*102 infinite combination exists for us and we are not sure.

So to proceed we say ok for n=3 we have 4 multiplication and they say this 4 can be written in as a*b*c/2 or a*b*c/3 or a*b*c/6. (assume a,b,c are consecutive no)

So now you write 4 = 1*2*2 say and multiply by 2 to check option A is satisfied or not 1*2*2*2 we see we can’t write this factor as a*b*c, similarly for option B multiply 1*2*2*3 again you can’t write and now check for option C 1*2*2*6 = 2*3*4 so yeah we can write this in term of 3 consecutive numbers so this is answer. BUT since NONE OF THE ABOVE is in the option we can never be sure if C is always correct or not, if NONE of the above was not in option we can definitely be sure but although in exam this risk is worth it because no one has time to derive those results and many won’t know how to derive

---

Don’t know anything watch this.

---

This kind of loops can be thought similar to ball and buckets problem where range of i (1 to n) corresponds to n number of buckets and r number of loop variables corresponds to r balls.

Total no of loop executions are$\large _{}^{n+r-1}\textrm{C}_{r}$ .(Check from Rosen page no 427 for more explanation)

Now in this question, total number of loop executions = $\large _{}^{n+3-1}\textrm{C}_{3}$

but we have counted extra executions cause k = j+1 to n not j to n , So we have to subtract those cases which is $\large _{}^{n+2-1}\textrm{C}_{2}$ (cause we have to subtract those cases where i <= j = k so j,k can be thought as one variable)

So total number of multiplications to be performed = $\large _{}^{n+2}\textrm{C}_{3}$ – $\large _{}^{n+1}\textrm{C}_{2}$ = $\large \frac{(n+1).n.(n-1)}{6}$

---

Same channel as suggest by realdonaldtrump. This one will help is expanding the second stage summation

https://www.youtube.com/watch?v=vGQMmpTInPU

---

Can we use this summation method of evaluations when step size is other than 1 (Means here all the 3 loops is incrementing 1 at a time).

If yes then how?? help….

---

@Manu+Thakur

Thankyou sir!

---

Hqw to solve this question in exam within 3 minutes

does anyone have another approach to solve this question

Answer 1

Total number of multiplications

$= \displaystyle \sum_{i=1}^{n}\sum_{j=i}^{n}\sum_{k=j+1}^{n} 1$
$= \displaystyle\sum_{i=1}^{n}\sum_{j=i}^{n}(n-j)$
$=\displaystyle \sum_{i=1}^{n}(n-i) + (n-(i+1)) + \ldots+ (n-n)$
$\displaystyle =\frac{1}{2}\sum_{i=1}^{n}(n-i)(n-i+1)$
$\displaystyle =\frac{1}{2}\sum_{i=1}^{n}(n^{2} +n+i^{2}-(2n+1)i)$
$\displaystyle = \frac{1}{2} \left( n^3 + n^2 + \sum_{i=1}^{n}i^2 - (2n+1). \sum_{i=1}^{n} i \right)$
$\displaystyle=    \frac{1}{2} \left( n^3 + n^2 + \frac{n. (n+1). (2n+1)}{6} - (2n+1). \frac{n. (n+1)}{2} \right)$
$ \displaystyle = \frac{1}{2} \left( n^3 + n^2  - \frac{n. (n+1). (2n+1)}{3} \right)$
$\displaystyle =  \frac{n}{6} \left( 3n(n+1)   -  (n+1). (2n+1) \right)$
$ \displaystyle= \frac{n. (n+1)}{6} (n-1)$
$ \displaystyle =\frac{(n-1)n(n+1)}{6}$

Therefore, correct answer would be (C).

Comments

how (n-i) on second step, anyonw can say any video reference for study this methoad

---

Amazing explanation…😊

---

@suvasish pal

Look at the summation range it changes from j=i to n     ------- > j=0 to (n-i)

we basically shifting backward from intital j=i to j=0 So, every occurrence of j must be replaced with n-j.

So, $\sum (n-j)$ is becoming $\sum (n-(n-j))$ and finally to $\sum j$

 

Answer 2

 

Same as Best answer, but I Cleared some Basic steps more.

Comments

why 1 is added while calculating n-j i don't understand that thing.

---

e.g. if we want to sum from 2  to 9 then total objects = (9-2)+1 = 8

likewise from j+1 to n will be n - (j+1) +1 = n - j

---

correct me if i am wrong.

Answer 3

i goes 1 to n

j goes i to n

k goes j+1 to n

let's take first iteration for i: as i=1

j goes 1 to n

for j=1 , k: 2 to n = (n-1) times
    j=2 , k: 3 to n = (n-2) times
    ...
  j=n-1 , k: n to n = 1 time
  j= n  , k: 0 times

so, for i=1,
 number of multiplications : 1 + 2 + ... + (n-1)

similarly for i = 2,
 1+2+ .... + (n-2)

and so on,

for i = (n-1)
   1

for i = n
  0

so, for every i say last term as T

we have for every i, 1+2+3+... + T = T(T+1)/2 = (T^2  + T)/2

where T goes from 1 to (n-1)

∑  (T^2  + T)/2 , T goes 1 to (n-1) = (n-1)(n)(n+1)/ 6

so, option C is correct

Comments

Nice answer

Answer 4

C

Take a simple example with n=3

It will give 4multiplications. For verification take other example with n=4.

Only choice which satisfy is c

Comments

OK I got it. we have to take n=3, then use (2*3*4)/6 for checking option D. I was doing a mistake in unrolling the for loops.

---

In your method in order to calculate product of 3 consecutive numbers which formula to use
(N*(N+1)*(N+2)) or ((N-1)*(N)*(N+1))?  both gives different ans

---

Total multiplications with n= 4 is coming 10