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

But three consecutive integers can be anything here it is not mentioned about n

---

Simplest way is, Take n=2 for that K loop executes 1 time so Mul. is done 1 time ,

take 3 consecutive int. product 1*2*3 =6 and check for which option value1 comes , hence C

---

So answer should be C

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

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$

 

---

https://youtu.be/bwe3Y_NO0u8?feature=shared   video solution

Answer 2

 

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

Comments

correct me if i am wrong.

---

How did you get the values for the consecutive integers? @Emankashyap

---

great explanation

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

---

most understanding and intuitive answer, thanks brother

---

This is how the steps take place after the loop analysis is done.
For my future reference

---

10 years ago, on this exact day, someone answered this question in such a simple way. Take a bow for simplifying this question so much.

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

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

---

@Warlock lord The " Best Comment "

Answer 5

i	j	Inner Loop Iternations
1	1	n-1
1	2	n-2
1	..	..
1	..	..
1	n	0

i	j	Inner Loop Iterations
2	2	n-2
2	3	n-3
2	..	..
2	..	..
2	n	0

i	j	Inner Loop Iterations
n-1	n-1	1
n-1	n	0

i	j	Inner Loop Iternations
n	n	0

Total Number of Inner Loop iterations = (0) + (0+1) + (0+1+2) + (0+1+2+3) +............+ (0+1+2+3+....n-1)

= ∑i=0 to n-1   (0+1+2+.....i)  

= ∑i=0 to n-1   (i*(i+1))/2

= ∑i=0 to n-1   (i² + i)/2

= [ (n-1)(n)(2n-1)/6 + (n-1)n/2 ] / 2

= (n-1)n(n+1)/6

Hence C option is the correct answer. 

Answer 6

Option C

When difference of the terms of the series form an A.P., then how to write any random term for that series ?

Source :  https://math.stackexchange.com/questions/1961952/how-do-i-find-the-sum-of-a-sequence-whose-common-difference-is-in-arithmetic-pro

Note : There are n-1 terms in the series, I took n terms for easier calculation. It won't affect the answer at all.