The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+36 votes
6.2k 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.
asked in Algorithms by Veteran (103k points)
edited by | 6.2k views
+14

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

9 Answers

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

answered by Loyal (5.7k 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 !!
+6
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.
+4

similar way...

+6
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 ...
+19 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

answered by Boss (15.5k points)
0
Nice answer
+15 votes

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

answered by Loyal (9k points)
+2
Best answer for me : ) Thanks.. very well explained!

Keep posting such answers, it helps much!
0
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.
+14 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
answered by Loyal (8.1k 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?
+1
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....
+8 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. 

answered by (173 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

answered by Loyal (8.5k points)
0 votes

The total number of multiplications to be performed will be equal to the number of times the inner-most loop executes , ie , the loop with 'k' as the counter variable.

When i=1, j=1, then the 'k' loop executes (n-1) times
i=1 , j=2 , => (n-2) times
....
=> for i=1 , the no of multiplications is = (n-1) + (n-2) + .... + 2 + 1 = ∑(n-1)

for i=2 , similarly , the no of multiplications = ∑(n-2)

...

for i=n-1 , the no of multiplications = ∑1 = 1

Hence , the total no of multiplications is = ∑(n-1) + ∑(n-2) + .... + ∑(2) + ∑(1)

=(1+2+... +n-1) + (1+2+...+n-2) + .... + (2+1) + (1)
=Sn-1 + Sn-2 + ... + S2 + S1
=∑Si (from i=1 to n-1)
=∑[n*(n-1)/2]
=∑[(n2)/2] - ∑[(n)/2]
= (n)(n+1)(2n+1)12−n(n+1)4=(n−1)(n)(n+1)6

ANSWER : (C) One-sixth of the product of the 3 consecutive integers.

Source:http://www.techtud.com/example/consider-following-pseudo-code-gate-2014

answered by Active (3k points)
0
How did you do the summation , it was varying in terms of i , but you internally wrote n(n-1)/2 , how you got this , please explain briefly .
0 votes

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. 

 

 

 

answered by (195 points)
0 votes

Answer is C

answered by (341 points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

40,994 questions
47,622 answers
146,900 comments
62,346 users