+50 votes
11.5k views

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 
1. Half of the product of the $3$ consecutive integers.
2. One-third of the product of the $3$ consecutive integers.
3. One-sixth of the product of the $3$ consecutive integers.
4. None of the above.

edited | 11.5k views
+53

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

0
Thanks xD
+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
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?
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.

## 10 Answers

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

by
edited by
+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 !!
+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.
+2
very good explaination...tanq so much.
+6

similar way...

+14
If we start at (j+1) and end at n, total count be  n - (j+1) + 1 = n-j
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.
+1
Can you please explain how in the 3rd step (n-j) becomes j?
+3

papesh can u describe how (n-j) become j ?

0
I don't understand. Where I can read about how you simplified summation.
0
I have the same doubt how n-j becomes j
0
Substitute m = n -j

when j = i .. m = n - i

when j = n  ... m = n - m ...

Now call m as j ...
0
Please explain the 6th line how n^2 have become n^3 and n has become n^2?
0
We are adding $n$ times $n^2$, that is why $\sum n^2$ becomes $n^3$.
0
On clearly observing it is summation of

(n-1) + (n-2) + .....1

(n-2) + (n-3) + .......1

(n-3) + (n-4) +.......1

.

.

.

so on

1

equal to

Sigma(n=1 to n) (n(n-1))/2

1/2(Sigma(n^2) - Sigma (n))

1/2((n*(n+1)*(2n+1))/6 - n(n+1)/2)

on solving finally we get

(n(n-1)(n+1))/6
0
how (n-i) on second step, anyonw can say any video reference for study this methoad
+29 votes

Same as Best answer,But i Cleared some Basic steps more.

+3
Best answer for me : ) Thanks.. very well explained!

Keep posting such answers, it helps much!
+1
can u send more clear picture?
+1
@junaid ahmad your answer is best answer. Thanks for helping people like me who are poor at math.
0
why 1 is added while calculating n-j i don't understand that thing.
0
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
+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

0
Nice answer
+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
by
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?
+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.
+1
Best !!
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....
0
How are we getting 4 multiplications after taking n = 3? Someone please elaborate, because I am getting 9 multiplications and I don't know where I am going wrong.
0
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.
+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+ 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 = n2 + (n-1)2 + .. 12. 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

+1 vote

Option C

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

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

by
+1 vote

here i have taken n = 3, unrolled the for loops and then checked the options. Answer is  OPTION D

Answer:

+54 votes
13 answers
2
+22 votes
3 answers
4