## bdknight

The most efficient answer is to not use divide at all. Basically you need 1 temporary array and 1 result array, and 3 loops.

Assuming input array is a, length is n.

The first loop is to put a[0] * a[1] *...*a[i-1] into temp[i]

The second loop starts from the end of the array, put a[i+1] * a[i+2] *...*a[n] into result[i];

The third loop do result[i] *= temp[i], which makes result[i] = a[0] * a[1] * ... * a[i-1] * a[i+1] *... a[n].

T(i) is the # of permutation of BST for {1, 2, ... i}.

Now consider {1, 2, ..., n}, if you pick element x (1<= x <= n) as your BST's root node, then the BST permutation when x is root node is the permutation of left and right subtree together:

T(x-1) + T((x+1) ~ n).

Looking the right subtree, since all element is greater than x in the right subtree (BST definition), let's substract x from all elements, then T((x+1) ~n) become T(1~(n-x)) = T(n-x). Hence picking x as root node has the permutation of

T(x-1) + T(n-x).

The algorithm can hence be described recursively as

```
int T(int x)
{
if (x = 0) return 0;
if (x = 1) return 1;
int result = 0;
for (i =1; i <= x; i++)
{
result += T(i - 1) + T(x - i);
}
return result;
```

You can further optimize it by doing dynamic programming and storing all intermediate T(x) into a table

- bdknight September 18, 2012**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

Yes you were right. should replace all + with * here.

- bdknight September 19, 2012