## Amazon Interview Question

SDE1s**Country:**India

**Interview Type:**Written Test

I did the algebra for these summations got this result:

`((m-1)*((n*l) - ((l*m)/2) - (2 * l) - ((3/2)*n) - ((1/4)*m) - 3 - ((n**2)/2) + (((2*(m**2)) - m)/6)))`

However, this does not produce the same results as the code, unfortunately. For instance, m=2; n=4; l=6 produces -8 instead of the desired 14

Maybe I made a mistake? I think the algebra is quite sound. I think the equation is wrong somehow...

we will have to solve this equation

m-1 n-1 l-1

Σ Σ Σ 1

i=0 j=i+1 k=j+1

=

m-1 n-1

Σ Σ ( l - j -2)

i=0 j=i+1

m-1

Σ (l-2)*(n-i-2) - (n^2/2 - n/2 - i^2/2 + i/2)

i=0

Solve the last equation and you will get the actual answer.

According to Wolfram Alpha (wolframalpha.com), the sum you state is equal to 0.

http://www.wolframalpha.com/input/?i=sum+from+i%3D0+to+m-1+of+%28l-2%29*%28n-i-2%29+-+%28n%5E2%2F2+-+n%2F2+-+i%5E2%2F2+%2B+i%2F2%29

I did the algebra for these summations and got the same penultimate result, and then solved the final summation and got:

`((m-1)*((n*l) - ((l*m)/2) - (2 * l) - ((3/2)*n) - ((1/4)*m) - 3 - ((n**2)/2) + (((2*(m**2)) - m)/6)))`

However, this does not produce the same results as the code, unfortunately. For instance, m=2; n=4; l=6 produces -8 instead of the desired 14

summation over(n-1)(l-2)+(n-2)(l-3)+(n-3)(l-4)...(n-Z)(l-Z-1).... m times or till n-Z or l-Z-1 becomes negative

this has close form solution

summation (n-z)(l-z-1) = nl + z^2 +z - lz-nz-n

= nl + z^2 - (l+n-1)z -n

this summation can be calculated over 1-> Z

where Z = min(m,n,l-1)

the summation is

Zn(l-1) + Z*(Z+1)*( 2Z - 3l -3n +4)/6

Z=min(m,n,l-1)

test if any doubt

The answer is 1!+2!+---+ (l-2)!. I too could not find it directly. I had to debug and understand how the loop runs. It was completely dependent on the 'L' and not dependent on M and N. and by the way, since l-2 will be positive only when l>=3, the answer for l<=2 is 0.. for eg: if l = 6, then value is 1!+2!+3!+4! = 20..and for l=7 it will be 35.. and so on..

You can check it out..

Sorry i get the symbol wrongly.. i meant sum of integers not the factorial.. ∑(∑n) where n = 1 to l-2.. for the same example l = 6, sum of 1 to sum of 4..

Yes, I have already mentioned that case in the answer.. as l-2 will be positive only if l >2, the value will be 0 for any value of l that <= 2

mrange = min(m, l-2)

Σ[(l-i-2)(l-i-1)/2] from 1 to mrange

sum = mrange*(mrange+1)*(2*mrange+1)/12 + mrange*(mrange+1)*(1-2*l)/4 + mrange*l*(l-1)/2;

The closed form can be further reduced.

{

int ComputeFormula(const int& m, const int& n, const int& l) {

int mrange = std::min(m, l-2);

mrange = std::min(mrange, n-1);

int cstCorr = 0;

if(l > n) {

cstCorr = (l-n-1)*(l-n)/2;

}

return mrange*(mrange+1)*(2*mrange+1)/12 + mrange*(mrange+1)*(1-2*l)/4 + mrange*(l*(l-1)/2 - cstCorr );

}

}

This must work. Please challenge it.

In C++

```
// ConsoleApplication3.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
#include <algorithm>
using namespace std;
double Sum(int k, int l, int m)
{
double total = 0;
int x= min(l-1, m-1);
int y = min(x, k);
total = (y) * m * x - m*(y*(y-1))/2 - (y) * ((x+1)*(x+2)) / 2 + y * (( y * (y +1))/2) - ( ((y+1)* y * (2*y +1))/6 - (y*(y+1))/2);
return total;
}
int _tmain(int argc, _TCHAR* argv[])
{
int k = 1;
int l = 2;
int m = 3;
int sum = 0;
for(int i=0; i< k; i++)
for(int j= i+1; j< l; j++)
for(int z=j+1; z < m; z++)
sum++;
cout << sum << endl;
cout << Sum(k,l,m)<< endl;
getchar();
return 0;
}
```

Outputs

10

10

1. First of all the condition should be: {n > 1 and l > n}

2. After solving the summation: (sum from i=0 to m-1 (sum from j = i+1 to n-1 (sum from k = j+1 to l-1 {1} ))), the result would be:

sol = sol1 - sol2 + sol3/12 - sol4, where

sol1 = (((l*n)-l)-n+1)*m;

sol2 = l*m*(m-1)/2;

sol3 = (9*m*(m-1)) + (m-1)*m*(2*m-1);

sol4 = n*(n-1)*m/2;

This could be further simplified..

If the answer is negative, then the sum would be 0

should be 0 since for (int k = j + 1; k < l; k++) is never to execute that k always not ( k < 1 )

Dude: I think you didnt get the question the right way. The solution you have provided goes for these kind of loops:

Notice that the lengths of inner loops are not independent, these are depending on the iterating variables of the outer loops.

```
for (i = 0; i < m; i++)
for (j = 1; j < n; j++)
for (k = 2; k < l; k++)
sum++;
```

We will have to solve this equation:

- Sunny January 05, 2014m-1 n-1 l-1

Σ Σ Σ 1

i=0 j=i+1 k=j+1