Gold Chain – techinterview

⏱ 2 min read

A man has a gold chain with 7 links. he needs the service of a laborer for 7 days at a fee of one gold link per day. however, each day of work needs to be paid for separately. in other words, the worker must be paid each day after working and if the laborer is ever overpaid he will quit with the extra money. also he will never allow himself to be owed a link.

what is the fewest # of cuts to the chain to facilitate this arrangement and how does that guarantee payment?

Solution

Can we get change back from the laborer?

If so, we cut one link to make a chain of 4 links, a chain of 2 links and the cut link itself.

Day 1, we give him the cut link
Day 2, we take back the cut link, give him the 2 link chain
Day 3, we give him the cut link
Day 4, we take back both the cut link and the 2 link chain, give him the 4 link chain
Day 5, we give him the cut link
Day 6, we take back the cut link, give him the 2 link chain
Day 7, we give him the cut link

2026 Update: Greedy Algorithms and Change-Making

The Gold Chain puzzle (you have a 23-link chain and must pay exactly 1 link per day for 23 days of hotel — what is the minimum number of cuts to make?) is a greedy/binary representation problem. The optimal solution is to cut links 1, 2, 4… in a pattern that allows you to make exact change for any amount up to 23, just like binary number representation.

The minimum cuts insight: With cuts at links 1, 3, 8… you can represent any value 1-23 as a combination of these pieces. This is exactly the problem of finding a minimal set of denominations that covers all values up to N — the same as optimal banknote design.

def min_cuts_for_chain(n):
    """
    Find minimum cuts to pay exactly 1..n units per day.
    Equivalent to: find smallest set of numbers that sum to n
    and can represent all values 1..n through subset sums.
    Greedy: each piece should be 1 + sum_of_previous_pieces.
    """
    pieces = []
    remaining = n

    while remaining > 0:
        next_piece = sum(pieces) + 1  # Can cover 1 more than current total
        next_piece = min(next_piece, remaining)
        pieces.append(next_piece)
        remaining -= next_piece

    return pieces

pieces = min_cuts_for_chain(23)
print(f"Cut into pieces: {pieces}")  # [1, 2, 4, 8, 8] or similar
print(f"Number of cuts: {len(pieces) - 1}")  # n-1 cuts for n pieces

Modern application: This is essentially the coin change problem variant of “design the minimum number of coin denominations to make exact change for all values 1-N.” It appears in: payment system denomination design, address space layout in OS memory management, and time-of-use pricing tier design.

💡Strategies for Solving This Problem

The Payment Problem

Classic logic puzzle. You have a gold chain with n links and need to pay someone 1 link per day for n days. What's the minimum number of cuts needed?

The Problem Setup

Gold chain has n links in a row. You need to pay 1 link per day for n days. You can make cuts to create pieces, and pieces can be traded back and forth.

Example: 7 links, need to pay 1/day for 7 days. How many cuts minimum?

Key Insight

You can get pieces back! Day 1: give 1 link. Day 2: give 2-link piece, get 1 link back. Day 3: give that 1 link back (now they have 3 total).

This is like representing numbers in base 2, but with "trading back" allowed.

The Pattern

With k cuts, you get k+1 pieces. You can pay up to 2^k - 1 days if pieces are sized correctly.

Optimal piece sizes: 1, 2, 4, 8, ... (powers of 2)

For n links, need ceiling(log2(n+1)) cuts.

Example: 7 Links

Make 2 cuts to create pieces of size 1, 2, 4:

Day 1: Give 1
Day 2: Give 2, take back 1
Day 3: Give 1 (they have 3)
Day 4: Give 4, take back 1 and 2
Day 5: Give 1 (they have 5)
Day 6: Give 2, take back 1
Day 7: Give 1 (they have 7)

Answer: 2 cuts for 7 links.

At Various Companies

This is more of a logic puzzle than coding problem. Tests your ability to see patterns and think about state representation. Similar to making change with coins problem.

✅Solution

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