bdknight
BAN USERThe 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
Yes you were right. should replace all + with * here.
- bdknight September 19, 2012