CareerCup

Each time, you combine two sticks of min length, you have (N-2) + 1 (the new stick) = N-1 left in system. So now you re-calculate and choose 2 min sticks and combine those and continue.

Implementation:
Use a min-heap, remove min and next min = combine, insert the new length into the heap.
worst case Per operation runtime: 2*log (N) (remove 2 mins) + log (N) (insert new value)

Operation repeated N times = 3N*log(N) = O(N log(N))

However, if you notice, the height of min-heap goes on decreasing in each step and a more tighter analysis would yield a log(N!) worst case complexity (which ofcourse is O(N*log(N))

EDITED: there is flaw in my post! The order of sticks matters!

Re-formulate the problem:

Given n sticks of length L_1, L_2, ..., L_n, with total length of L.
Only combination of two sticks into one is allowed each time. Every combination costs the sum of the two sticks.

Calculate the minimum cost to combine all n sticks into a stick of length L.

This can be solved by recursive/DP as following.

Let C(u,v) be the minimum cost to join sticks from number u to number v.
The recursive formula will be:

C(u,v) = min { C(u,k) + C(k+1,v) }, for k = u+1 to v-1;

The answer will be C(1,n).

My pseudo code implementation using recursive with memoization:

joinSticks(u,v):

if (u == v) return L[u];
if (Mem[pair(u,v)] != 0 ) return Mem[pair(u,v)];

minCost = maxInt;
for k = u to v-1
	minCost = min { minCost, joinSticks(u,k) + joinSticks(k+1,v) };

Mem[pair(u,v)] = minCost;

return minCost;

Recursively pick the two sticks of minimum length, merge it (e.g. sum value) and add it back to the collection.

The reason why you should always pick the minimum 2 length is:

1, suppose you have two sticks, a1 and a2
the cost is a1 + a2

2, suppose you have three sticks, a1 < a2 < a3
the answer is you pick a1, a2 first, the cost is 2*(a1 + a2) + a3
why if you choose a3 first? the cost would be higher than above by:
2 * (a3 - a2) - (a3 - a2) = a3 - a2, which is a positive value.

So you should always pick the minimum 2 sticks.

1, Sort the array
2, pick the first two
3, insert the sum of first two to the sorted array (log n)

repeat that steps until done
total cost is nlogn

I think the problem can be better explained with an example as many people are thinking that the total cost will be sum of all the lengths. Suppose there are 3 sticks of length 1, 2, 4

You can do the combination in this way,

Step 1: 1+2 (cost=3) Now we have two sticks of length 3 and 4
Step 2: 3+4(cost=7) Now we have one stick of length 7
Total cost 7+3=10

But if you do it in this way,
Step 1: 4+2 (cost=6) Now we have two sticks of length 6 and 1
Step 2: 6+1 (cost=7) Now we have one stick of length 7
Total cost 6+7=13

So we can see that if we add the smaller ones first, we will minimize the cost. We can solve it with a min heap. We will add all the lengths in the min heap. We will pop two from the min heap and add them and put them back in the heap. We will continue this process till there is no more stick.

I think the key is:
1. sort the sticks in ascent order, L1 <= L2 <= L3 <=...Ln
2. each time when combined 2 sticks, then put it back to the pool, and sort it again as 1)
3. we can see if the each time combination is smallest, the summary of all costs number is smallest.

As there is no restrictions on the order of sticks mentioned so perhaps sorting them in ascending order and start combining from the least one will give the minimum cost.
suppose the length of sticks are x1,x2,x3,x4.........,xn then the total cost will be given by (x1 + x2) + (x1+x2+x3) + (x1+x2+x3+x4)+...........+(x1+x2+x3+..........+xn)
So to have the minimum value x1,x2,x3......,xn must be in increasing order.

#include <stdio.h>
#include <stdlib.h>
#define INF (~0)

/* This can be optimized by caching */
unsigned int stick_length(int sticks[], int s, int e)
{
    unsigned int i, ans = 0;
    
    for (i = s; i <= e; i++) {
        ans += sticks[i];
    }

    return ans;
}

unsigned int join_sticks(int sticks[], int s, int e, unsigned int **cache)
{
    int k, p1, p2, tmp;

    if (s > e) return INF;
    if (s == e) return sticks[s];

    if (cache[s][e] != INF) {
        return cache[s][e];
    }

    for (k = s; k < e; k++) {
        p1 = join_sticks(sticks, s, k, cache);
        p2 = join_sticks(sticks, k+1, e, cache);

        /* adding stick lengths, not same as making cost */
        tmp = stick_length(sticks, s, k) + stick_length(sticks, k+1, e);

        /* adding making cost */
        if (k > s) tmp += p1;
        if (k+1 < e) tmp += p2;

        if (tmp < cache[s][e]) {
            cache[s][e] = tmp;
        }
    }

    return cache[s][e];
}

int main()
{
    int i, j;
    int sticks[] = {24, 25, 28, 4, 6, 10, 9};
    // int sticks[] = {2, 3, 4, 6};
    // int sticks[] = {2, 3, 4, 6, 7};
    // int sticks[] = {13, 4, 6};
    int n = sizeof(sticks)/sizeof(sticks[0]);
    unsigned int ans;

    unsigned int **cache;
    cache = (unsigned int **)calloc(n, sizeof(int *));
    for (i = 0; i < n; i++) {
        cache[i] = (unsigned int *)malloc(n*sizeof(int));
    }
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            cache[i][j] = INF;
        }
    }

    ans = join_sticks(sticks, 0, n-1, cache);
    printf("ans: %u\n", ans);

    return 0;
}

I can come up with a NlogN complexity algo if lengths given are in random order.
Incase the lengths are sorted then complextity would be O(N)

Lengths = Array.Sort(Lengths)
int [] IncrementalLength = new int[Lengths.length + 1]
for(int i=1;i<=Lengths.length;i++)
  incrementalLength[i] = incrementalLength[i-1] + Lengths[i-1]

TotalSum = SumArray(incrementalLength)
return TotalSum

Solve it with a greedy algorithm similar to algorithm for Huffman tree.

Suppose there are n(>0) sticks of length {L1, L2, ... , Ln}, where L1<=L2<=...<=Ln, I think the answer is:
cost =
(1) 0, if n=1;
(2) L1+L2, if n=2;
(3) L1 + 2 * (L2 + L3 +...+Ln-1) + Ln, if n>2;
Prove:
Each time we combine 2 sticks to 1, there remains n-1 sticks, until there is only 1 stick. So we need to combine n-1 times. To minimize each combine cost, we should choose the shortest 2 sticks all the time.
So, the 1st combine cost is L1+L2, left n-1 sticks of lenght {L2, L3, ... , Ln};
the 2nd combine cost is L2+L3, left {L3, L4, ..., Ln};
the 3rd combine cost is L3+L4, left {L4, L5, ..., Ln};
...
the total cost is L1+2*(L2 + L3 +...+Ln-1)+Ln.

If you take the long stick and start to devide it to parts and pay every time the stick length, the best way to do it, it to devide to two equal parts every time.

Do reverse of it and i think you would get the best solution.

Dupe: 14485666

I don't get it?
The answer is always sum of overall stick
It's independent of choices leading to the final sum.
It's not even a minimization problem.

for loop in any order over the sticks, and return the accumulated sum.

People, I got this from glassdoor. It is not from an interview I did!

Sort the array and then calculate the cost adding element starting from the lowest length.

You have an array of stick lengths,
sLen = {1, 4, 6, 10, 11 }.
If you remember your math, Addition is Commutative and Associative, i.e.
((1 + 4) + (6 + 10) + 11) == ((1 + 4) + (6 + (10 + 11)). The minimum cost is the same no matter how you do it. Unless you multiply two lengths that make up one piece and add the cost of each piece. Only in the latter case the answer will be different.

The final cost it's always the same (sum of lengths) regardless of the order segments are put together.

Let's say we have 3 segments

x < y < z

. The cost is

x + y + z

and you can compute it in several ways:

(x + y) + z = x + y + z
  x + (y + z) = x + y + z 
  y + (x + z) = x + y + z

I think,

finally for it to become a stick we have to combine all of them,
hence there is no minimum/maximum,
the cost will be the sum of all the elements(length of sticks).

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)