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

The Gateway to Computer Science Excellence

+42 votes

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

- Half of the product of the $3$ consecutive integers.
- One-third of the product of the $3$ consecutive integers.
- One-sixth of the product of the $3$ consecutive integers.
- None of the above.

+70 votes

Best answer

Total number of multiplications

$= \sum_{i=1}^{n}\sum_{j=i}^{n}\sum_{k=j+1}^{n} 1$

$= \sum_{i=1}^{n}\sum_{j=i}^{n}(n-j)$

$\\= \sum_{i=1}^{n}(n-i) + (n-(i+1)) + \ldots+ (n-n)$

$\\ =\frac{1}{2}\sum_{i=1}^{n}(n-i)(n-i+1)$

$\\ =\frac{1}{2}\sum_{i=1}^{n}(n^{2} +n+i^{2}-(2n+1)i)$

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

$\\ = \frac{1}{2} \left( n^3 + n^2 + \frac{n. (n+1). (2n+1)}{6} - (2n+1). \frac{n. (n+1)}{2} \right)$

$ \\ = \frac{1}{2} \left( n^3 + n^2 - \frac{n. (n+1). (2n+1)}{3} \right)$

$\\ = \frac{n}{6} \left( 3n(n+1) - (n+1). (2n+1) \right)$

$ \\= \frac{n. (n+1)}{6} (n-1)$

$ \\ =\frac{(n-1)n(n+1)}{6}$

Therefore, correct answer would be (**C**).

+1

What does it mean by "three consecutive integers" in this question? Which three consecutive integers are they talking about in the options?

+6

They don' mean any specific set of integers. Rather you can see as the answer contains product of n,(n-1) and (n+1) which are nothing but "three consecutive integers" for some 'n' taken as upper bound for iteration in the loop.

Hope it clears !!

Hope it clears !!

+9

Is there any simple method for solving this problem other than this? Please tell me? This is not useful answer for me? There are so many complications in this answer. Please guide me.

0

The substitutions used in the proof are pretty straight forward and needed for many other questions too. Still, if you want to avoid them, just try substituting the options.

0

for k = j + 1 to n do

This statement implies that k would run for n-j different values (starting at j+1 and ending at n).

+3

I'm not getting your doubt. If you describe what line you are not understanding and what do you think about that line then I would be able to clear your doubt.

+27 votes

+1

+22 votes

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

+15 votes

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

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

0

That is fine taking values of n and computing the number of multiplication. But how you select the options?

For example, if n= 3 for option a) Half of the product of the 3 consecutive integers. which 3 consecutive integers you will choose?

For example, if n= 3 for option a) Half of the product of the 3 consecutive integers. which 3 consecutive integers you will choose?

+4

the product of three consecutive is written as (n-1)*n*(n+1). Ex: 1*2*3 .. here n = 2. Now you may solve by substituting.

0

But for n=4, total number of multiplications are coming as 6, but while doing (3*4*5)/6 = 10. So both are not satisfying. Can you please suggest why it is failing for n=4. Whereas for n=3 it was satisfying.

0

Nandini gupta if we take n=4 then when i =1 then j=1 to 4 and for each value of j ....k repeat accordingly.similarly for i=2 nd so on....

+10 votes

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^{2 }+ 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.

+1 vote

The statement “D = D * 3” is executed **n*(n+1)*(n-1)/6** times. Let us see how.

For i = 1, the multiplication statement is executed (n-1) + (n-2) + .. 2 + 1 times.

For i = 2, the statement is executed (n-2) + (n-3) + .. 2 + 1 times

………………………..

……………………….

For i = n-1, the statement is executed once.

For i = n, the statement is not executed at all

So overall the statement is executed following times

[(n-1) + (n-2) + .. 2 + 1] + [(n-2) + (n-3) + .. 2 + 1] + … + 1 + 0

The above series can be written as

S = [n*(n-1)/2 + (n-1)*(n-2)/2 + ….. + 1]

The sum of above series can be obtained by trick of subtraction the series from standard Series S1 = n^{2} + (n-1)^{2} + .. 1^{2}. The sum of this standard series is n*(n+1)*(2n+1)/6

S1 – 2S = n + (n-1) + … 1 = n*(n+1)/2

2S = n*(n+1)*(2n+1)/6 – n*(n+1)/2

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,647 questions

56,505 answers

195,505 comments

100,876 users