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

+50 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.

+53

+4

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

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

0

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?

Will it be a correct approach?

0

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.

+74 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?

+8

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 !!

+10

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.

+29 votes

+1

+24 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?

+5

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

+12 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.

+2 votes

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

52,375 questions

60,581 answers

201,992 comments

95,398 users