Gold Chain

Solution: Minimum Cuts

function minimumCuts(n) {
    // With k cuts, we get k+1 pieces
    // We can pay for 2^k - 1 days if pieces are powers of 2
    // So we need k such that 2^k - 1 >= n
    // Which means 2^k >= n + 1
    // So k >= log2(n + 1)

    if (n <= 0) return 0;
    if (n === 1) return 0;  // No cuts needed for 1 link

    return Math.ceil(Math.log2(n + 1)) - 1;
}

// Tests
console.log(minimumCuts(1));   // 0 cuts (just give the link)
console.log(minimumCuts(3));   // 1 cut (pieces: 1, 2)
console.log(minimumCuts(7));   // 2 cuts (pieces: 1, 2, 4)
console.log(minimumCuts(15));  // 3 cuts (pieces: 1, 2, 4, 8)
console.log(minimumCuts(31));  // 4 cuts (pieces: 1, 2, 4, 8, 16)

Generate Cut Positions

function getCutPositions(n) {
    const cuts = [];
    let position = 1;

    while (position < n) {
        cuts.push(position);
        position *= 2;
    }

    return cuts;
}

// For 7 links: cut after position 1 and position 3
// Creates pieces: [1], [2], [4]
console.log(getCutPositions(7));   // [1, 3] (cut after 1st and 3rd link)
console.log(getCutPositions(15));  // [1, 3, 7] (pieces: 1, 2, 4, 8)

Generate Payment Sequence

function paymentSequence(n) {
    // Generate pieces (powers of 2 up to n)
    const pieces = [];
    let size = 1;
    while (size <= n) {
        pieces.push(size);
        size *= 2;
    }

    // Track what worker has
    const workerHas = new Set();
    const sequence = [];

    for (let day = 1; day <= n; day++) {
        const payment = [];

        // What needs to be given/returned to reach 'day' total?
        // This is like binary representation of 'day'
        for (let i = 0; i < pieces.length; i++) {
            const piece = pieces[i];

            if (day & (1 << i)) {
                // This bit is set, worker should have this piece
                if (!workerHas.has(piece)) {
                    payment.push(`+${piece}`);
                    workerHas.add(piece);
                }
            } else {
                // This bit is not set, take back if worker has it
                if (workerHas.has(piece)) {
                    payment.push(`-${piece}`);
                    workerHas.delete(piece);
                }
            }
        }

        sequence.push(`Day ${day}: ${payment.join(' ')}`);
    }

    return sequence;
}

// Test for 7 links
paymentSequence(7).forEach(s => console.log(s));
/*
Day 1: +1
Day 2: +2 -1
Day 3: +1
Day 4: +4 -2 -1
Day 5: +1
Day 6: +2 -1
Day 7: +1
*/

Verification Function

function verifyPayment(n, pieces) {
    // Check if given pieces can pay 1..n
    const canPay = [];

    for (let target = 1; target <= n; target++) {
        // Try to make 'target' using subset of pieces
        let possible = false;

        // Use bitmask to try all subsets
        for (let mask = 0; mask < (1 << pieces.length); mask++) {
            let sum = 0;
            for (let i = 0; i < pieces.length; i++) {
                if (mask & (1 << i)) {
                    sum += pieces[i];
                }
            }

            if (sum === target) {
                possible = true;
                break;
            }
        }

        canPay.push(possible);
    }

    return canPay.every(x => x);
}

// Test
console.log(verifyPayment(7, [1, 2, 4]));     // true
console.log(verifyPayment(7, [1, 3, 3]));     // false
console.log(verifyPayment(15, [1, 2, 4, 8])); // true

Why Powers of 2 Work

Powers of 2 can represent any number through binary:

1 = 1
2 = 2
3 = 2 + 1
4 = 4
5 = 4 + 1
6 = 4 + 2
7 = 4 + 2 + 1
...

With pieces [1, 2, 4], we can make 1 through 7.
With pieces [1, 2, 4, 8], we can make 1 through 15.

Each number has a unique binary representation, so we can always make the target amount.

Non-Optimal Example

For 7 links, what if we cut differently?

3 cuts creating pieces [1, 1, 2, 3]: Can pay 1-7, but uses more cuts.

1 cut creating pieces [3, 4]: Can't pay day 1 or day 2. Doesn't work.

Powers of 2 are optimal!

Complexity

Minimum cuts: O(1) - just a log calculation
Payment sequence: O(n × log n) - n days, log n pieces
Verification: O(n × 2^k) where k is number of pieces

Related Problems

• Coin change: Similar binary representation idea
• Measuring water: Use jugs to measure amounts
• Balance scale: Find fake coin with minimum weighings