9.1k 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 | 9.1k views
+40

Simplified version of the selected answer for the people like me who are below the  poverty line in Maths: 0
Thanks xD
+3
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.

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 Loyal (6k points)
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?
+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 !!
+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.
+2
very good explaination...tanq so much.
+5 similar way...

+11
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 Same as Best answer,But i Cleared some Basic steps more.

by Loyal (8.5k points)
+3
Best answer for me : ) Thanks.. very well explained!

Keep posting such answers, it helps much!
0
can u send more clear picture?
+1
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

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

by Boss (15.6k points)
0
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 Loyal (8.2k points)
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?
+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.
+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.
 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.

by (185 points)
+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 = 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

by Loyal (9.7k points)
+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 (323 points)
+1 vote here i have taken n = 3, unrolled the for loops and then checked the options. Answer is  OPTION D

by (57 points)