CareerCup

I apologise for the delay in replying. The method convertToList(node *p) is basically a slight variant of the recursive inorder algorithm.
This converts a binary tree with root p into a linked list where nodes are ordered in inorder fashion. (Hence the first node will be the extreme left of the tree).
The leftHighest node is basically the largest node of p->left subtree if it were a BST (the rightmost node of p->left).
Once I convert subtree p->left to linkedlist (by recursion), I add p to the end of the list (using 'right' pointer).
Next, I convert p->right subtree to linkedlist (by recursion) and attach it to the end of the above tree. The first node of the former will be the lowest node of p->right (rightLowest) if it were a BST, which is the leftmost node of p->right.

Suppose L1,L2,...Ln are length of the sticks with L1 <= L2 <= L3 <= ... <=Ln.
No matter how you form the final stick, each stick is used twice except for the outer ones, which are used only once. Hence, any combination which puts the largest two sticks at the left & right ends will be an optimal one.

Minimal cost = 2*[ L1 + L2 + ... + L(n-2)] + L(n-1) + Ln

An arrangement having this cost: Ln,L1,L2,L3,...L(n-1)

static int getMaxIndex(int[] arr) {
	int left=0,right = arr.length-1;
	//arr[left] >= anything to left of it, arr[right] >= anything to right of it

	while(left<right-1) {
		int mid = (left+right)/2;
		if (arr[mid]<arr[mid+1]) left=mid+1; else right=mid;
	}

	if(arr[left]>arr[right]) return left; else return right;
}

I'm making use of the fact that two digits can be stored in a single character using 10*d1 + d2.

static void relocate(char[] arr) {
	int n = arr.length/2;
	char firstDigit = arr[1];

	//Replacing each digit char in 2nd half with INTEGER that combines two
	//consecutive digits as 10*(digit at pos-2) + digit
	//For example, if input is a0b1c2d3e4f5,
	//	char[11]=45,char[9]=23,char[7]=1 (integer equivalent)
	for(int i=2*n-1;i>n;i-=2) {
		arr[i] = (char)((arr[2*i-2*n+1]-'0') + 10*(arr[2*i-2*n-1]-'0'));
	}

	for(int i=1;i<n;i++) {//Move all letters to correct pos
		arr[i]=arr[2*i];
	}
	//From integers constructed above, extract the digits
	for(int i=2*n-1;i>n;i-=2) {
		arr[i-1] = (char)(arr[i]/10 + '0');
		arr[i] = (char)(arr[i]%10 + '0');
	}
	if(n%2 == 1) arr[n] = firstDigit;
}

call the method as attrib(lol); //lol = list of lists

void attrib(list<list<string> > &lol, list<string> &outlst = *(new list<string>)) {
	int n = outlst.size();
	if (n == lol.size()) {//outlst has attribute from last list
		for(list<string>::iterator itr=outlst.begin();itr!=outlst.end();itr++) {
			cout<<(*itr)<<'\t';
		}
		cout<<endl;
		return;
	}
	
	list<list<string> >::iterator lolItr = lol.begin();
	if (n) advance(lolItr,n);
	list<string> currlst = *lolItr;
	//Iterate over elements of n-th list.
	for(list<string>::iterator itr=currlst.begin();itr!=currlst.end();itr++) {
		outlst.push_back(*itr);
		attrib(lol,outlst);
		outlst.pop_back();
	}
}

Repeated subtraction is not an O(n) operation, depending on your implementation.

Nice solution but think the operations in the first loop are reversed. I mean, they should be
arr[i] = productSoFar;
productSoFar *= arr[i];

Thanks for all your comments! The logic I used is exactly as pointed out by aka.
In the first loop, I add (size * "OLD arr[arr[i]]") to arr[i] so that, when doing integer division by size, I get old arr[arr[i]], when doing %size, I get old arr[i]. However I add arr[arr[i]]%size to get old arr[arr[i]], in case it was already modified in the loop. The second loop simply replaces each arr[i] with old arr[arr[i]], as mentioned above.

void relocate(int *arr,int size) {
	for(int i=0;i<size;i++) {
		arr[i] += (arr[arr[i]]%size)*size;
	}
	for(int i=0;i<size;i++) {
		arr[i] /= size;
	}
}

class node{
public:
	int key;
	node* left;
	node* right;
	node(int key) {
		this->key = key;
		left = right = 0;
	}
};

node *degenerate(node *root) {
	if (!root) return 0;
	node *newroot = 0;
	for(newroot = root;newroot->left;newroot = newroot->left);
	convertToList(root);
	return newroot;
}

void convertToList(node *p) {
	node *leftHighest = 0;
	if (p->left) {
		for(leftHighest = p->left;leftHighest->right;leftHighest = leftHighest->right);
		convertToList(p->left);
		leftHighest->right = p;
		leftHighest->left = 0;
	}
	
	node *rightLowest = 0;
	if (p->right) {
		for(rightLowest = p->right;rightLowest->left;rightLowest = rightLowest->left);
		convertToList(p->right);
		p->right = rightLowest;
		p->left = 0;
	}
}