Ganesh Ram Sundaram
BAN USERSuppose 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(n2)] + L(n1) + Ln
An arrangement having this cost: Ln,L1,L2,L3,...L(n1)
static int getMaxIndex(int[] arr) {
int left=0,right = arr.length1;
//arr[left] >= anything to left of it, arr[right] >= anything to right of it
while(left<right1) {
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;
}

Ganesh Ram Sundaram
March 14, 2014 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 pos2) + digit
//For example, if input is a0b1c2d3e4f5,
// char[11]=45,char[9]=23,char[7]=1 (integer equivalent)
for(int i=2*n1;i>n;i=2) {
arr[i] = (char)((arr[2*i2*n+1]'0') + 10*(arr[2*i2*n1]'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*n1;i>n;i=2) {
arr[i1] = (char)(arr[i]/10 + '0');
arr[i] = (char)(arr[i]%10 + '0');
}
if(n%2 == 1) arr[n] = firstDigit;
}

Ganesh Ram Sundaram
March 10, 2014 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 nth list.
for(list<string>::iterator itr=currlst.begin();itr!=currlst.end();itr++) {
outlst.push_back(*itr);
attrib(lol,outlst);
outlst.pop_back();
}
}

Ganesh Ram Sundaram
March 08, 2014 Repeated subtraction is not an O(n) operation, depending on your implementation.
 Ganesh Ram Sundaram March 07, 2014Nice 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;
}
}

Ganesh Ram Sundaram
March 01, 2014 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;
}
}

Ganesh Ram Sundaram
February 24, 2014 Open Chat in New Window
I apologise for the delay in replying. The method convertToList(node *p) is basically a slight variant of the recursive inorder algorithm.
 Ganesh Ram Sundaram June 26, 2014This 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.