Loading…

mediumDynamic ProgrammingSometimes asked

Equal

Q: How do you solve Equal using the Brute Force — Coin DP toward the Minimum Only approach?

When to use it: Use it to establish the coin-change reduction is correct, then expose the target-selection bug it hides. Get the modelling right first, then see where the naive choice breaks. **The reduction (correct).** 'Add x to all-but-one' raises the group and freezes one person — relatively identical to subtracting x from that one person. So choose a common target `T` and, for each element, spend the fewest moves of size 1/2/5 to walk it down from `a[i]` to `T`. The cost of covering a difference `d` with denominations {1,2,5} is a classic minimum-coin-change problem, solvable with a small DP: `dp[v] = 1 + min(dp[v-1], dp[v-2], dp[v-5])`. **The naive choice (flawed).** The tempting target is `min(arr)` — surely you can't equalize below the smallest value for less? But you *can* spend operations to push elements below the current minimum, and that sometimes buys a cheaper coin breakdown. On `[1, 5, 5]`, targeting `min = 1` leaves differences `[0, 4, 4]`, costing `0 + 2 + 2 = 4` (each 4 = 2+2). Targeting `0` leaves `[1, 5, 5]`, costing `1 + 1 + 1 = 3` (each 5 is a single coin). The min-only version reports 4 — one operation too many. **Why it teaches the fix.** The coin reduction is sound; the error is fixing `T = min`. A difference that's awkward to make from one base (like 4 = 2+2) can become cheap from a base two lower (6... no — here 5 = one coin). So we should let the target dip slightly below the minimum and take the best. The next approach makes that precise. Time complexity: O(n · D). Space complexity: O(D).

Q: How do you solve Equal using the Greedy Coins over Three Targets (Optimal) approach?

When to use it: The answer they want. Phrase it as 'subtract-from-one → coin change, sweep targets min, min−1, min−2'. Combine the correct reduction with the right target search. **Per-element cost in O(1).** Because {1,2,5} is canonical, greedy is optimal: to cover a difference `d`, use `d/5` fives, then `(d%5)/2` twos, then `(d%5)%2` ones. So `coins(d) = d/5 + (d%5)/2 + (d%5)%2`. No table needed. **Sliding the target.** The remaining freedom is the common floor `T`. Lowering `T` increases every element's difference by the same amount, but coin costs are not linear in `d` — crossing a multiple-of-5 boundary can drop the cost. The known-tight result is that the optimum lies within two of the minimum, so we evaluate `T ∈ {min, min−1, min−2}` and take the cheapest total. **Why only three targets.** Decreasing `T` by 5 adds exactly one coin (one extra 5) to *every* element — never a saving. Within a window of 5, the only residues worth testing are offsets 0, 1, 2 from the minimum: offset 3 and 4 are equivalent (modulo the +1-per-5 effect) to offsets −2 and −1 of the next-lower multiple, already covered. So three targets exhaust the distinct cost profiles. **Walk-through of the win.** On `[1,5,5]`: `T=1` → diffs [0,4,4] → 0+2+2 = 4. `T=0` → diffs [1,5,5] → 1+1+1 = 3. `T=−1` → diffs [2,6,6] → 1 + 2 + 2 = 5. Minimum is 3, at `T = min−1`. The formula and the three-target sweep deliver it directly. Time complexity: O(n). Space complexity: O(1).

Q: How do you solve Equal using the Coin-Change DP per Target — Robust Variant approach?

When to use it: Mention when you're unsure the denomination set is canonical, or to show a greedy-free safety net. A defensive version that doesn't rely on greedy being optimal — useful if the denominations were, say, {1, 3, 4} where greedy fails. **Build the table once.** Compute `dp[v]` = minimum coins to make value `v` from {1,2,5} for every `v` up to the largest difference you could face, which is `max − (min − 2)`. The recurrence is the standard `dp[v] = 1 + min(dp[v−1], dp[v−2], dp[v−5])` with `dp[0] = 0`. **Reuse across targets.** For each target `T ∈ {min, min−1, min−2}`, total `dp[a − T]` over all elements. Because differences only shift by 0, 1, or 2, every needed index is within the precomputed range. **Why bother when greedy works here.** For {1,2,5} greedy is provably optimal, so this DP gives identical answers — it's strictly slower (O(D) build) but conceptually safer and immune to the canonical-system assumption. In an interview, lead with the greedy formula and mention this as the fallback for arbitrary denominations. **Correctness.** Coin-change-min DP is exact, and the three-target sweep is the same as the optimal approach, so the result matches the greedy version on every input. Time complexity: O(n + D). Space complexity: O(D).

Dynamic Programming · 34 of 44 · 11 min

Karen wants to make all of her colleagues' chocolate counts equal. In a single operation she may add 1, 2, or 5 chocolates to all colleagues except one of her choosing.

Given the initial array of chocolate counts, return the minimum number of operations needed to make every colleague's count equal.

In plain English

Adding the same amount to everyone except one person doesn't change how far ahead that one person is relative to the rest growing — equivalently, it lowers that one person relative to the group. So the only thing that matters is the gaps between people. We pick a common floor and figure out, for each person, the fewest moves of size 1/2/5 to bring them down to that floor. The clever bit is that the best floor might be just below the smallest current value.

Examples

Example 1

Input: arr = [2, 2, 3, 7]
Output: 2
Note: Reframe as lowering to min=2: differences [0,0,1,5]. Removing 1 costs 1 op, removing 5 costs 1 op → 2 operations total. (Equivalently: subtract 1 from the 3, subtract 5 from the 7.)

Example 2

Input: arr = [10, 7, 12]
Output: 3
Note: Target min=7: differences [3,0,5] → coins 2+0+1 = 3. Lower targets are worse here, so 3 is optimal.

Example 3

Input: arr = [1, 5, 5]
Output: 3
Note: Target min=1 gives differences [0,4,4] → 0+2+2 = 4. But target 0 gives [1,5,5] → 1+1+1 = 3. Going one below the minimum saves an operation.

Constraints

1 ≤ n ≤ 10⁴ (number of colleagues)
0 ≤ arr[i] ≤ 1000
Each operation adds exactly 1, 2, or 5 to all-but-one element
Multiple test cases may be batched

Clarifying questions4First question: Why can we treat 'add to all-but-one' as 'subtract from one'?Explore questions

Q1.Why can we treat 'add to all-but-one' as 'subtract from one'?
Adding x to everyone except person p raises the whole group by x and leaves p unchanged — that's the same *relative* outcome as lowering p by x. Since we only care about making counts equal (a relative condition), the two are interchangeable, and subtraction is easier to reason about.
Q2.Does the absolute final value matter?
No, only that all values match. That's why we can freely choose a target and why only the differences between elements drive the cost.
Q3.Why not always target the array minimum?
Because reaching a difference like 3 costs 2 coins (2+1), but if you lower the target by 2, that same element's difference might become 5 (one coin) while others only get slightly more expensive. Net savings are real — hence checking min, min−1, min−2.
Q4.Is greedy coin selection safe with {1, 2, 5}?
Yes. {1,2,5} is a canonical denomination system, so taking as many 5s as possible, then 2s, then 1s is provably minimal. For non-canonical sets you'd need a coin-change DP.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Each operation adds 1, 2, or 5 candies to *every colleague except one*. Adding the same amount to all-but-one is equivalent to *subtracting* that amount from a single person — so the relative gaps only shrink. The goal becomes: bring every element down to a common target using coins {1, 2, 5}, minimizing total coins. For a fixed target, the cost per element is a coin-change-min on its difference, and {1,2,5} lets a greedy fives→twos→ones split be optimal. The subtlety: the best target isn't always the array minimum — it can pay to go 1 or 2 below it. Try targets min, min−1, min−2 and take the cheapest total. O(n) time.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you spot that adding to all-but-one is equivalent to subtracting from one (making only differences matter), and then model the per-element cost as minimum coin change over {1,2,5}.

Where candidates slip

Assuming the target must be the array minimum — missing that min−1 or min−2 can be cheaper — or hand-rolling a wrong greedy that uses ones before twos.

How to stand out

State the subtract-from-one reframing explicitly, justify the greedy {5,2,1} split, and explain why scanning just three targets (min, min−1, min−2) is provably enough.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Coin DP toward the Minimum Only	`O(n · D)`	`O(D)`	Use it to establish the coin-change reduction is correct, then expose the target-selection bug it hides.	Read
2	Greedy Coins over Three Targets (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want. Phrase it as 'subtract-from-one → coin change, sweep targets min, min−1, min−2'.	Read
3	Coin-Change DP per Target — Robust Variant	`O(n + D)`	`O(D)`	Mention when you're unsure the denomination set is canonical, or to show a greedy-free safety net.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.Explore the full tree

From the puzzle to coin change

How to read it:Two reframings turn a confusing operation into a familiar subroutine.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 3

Brute Force — Coin DP toward the Minimum Only

TimeO(n · D)SpaceO(D)

Use it to establish the coin-change reduction is correct, then expose the target-selection bug it hides.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

First nail the reframing: adding to all-but-one is subtracting from one, so target a common value and pay per element to descend to it.

2Hint 2Explore hint

Pick the array minimum as the target and, for each element, compute the minimum number of {1,2,5} moves to cover its difference — a textbook coin-change-min DP.

3Hint 3Explore hint

Now stress-test it on [1,5,5]: targeting the minimum gives 4, but a lower target gives 3. The reduction is right; the fixed target is the flaw.

A · Core idea

Get the modelling right first, then see where the naive choice breaks.

The reduction (correct). 'Add x to all-but-one' raises the group and freezes one person — relatively identical to subtracting x from that one person. So choose a common target T and, for each element, spend the fewest moves of size 1/2/5 to walk it down from a[i] to T. The cost of covering a difference d with denominations {1,2,5} is a classic minimum-coin-change problem, solvable with a small DP: dp[v] = 1 + min(dp[v-1], dp[v-2], dp[v-5]).

The naive choice (flawed). The tempting target is min(arr) — surely you can't equalize below the smallest value for less? But you can spend operations to push elements below the current minimum, and that sometimes buys a cheaper coin breakdown. On [1, 5, 5], targeting min = 1 leaves differences [0, 4, 4], costing 0 + 2 + 2 = 4 (each 4 = 2+2). Targeting 0 leaves [1, 5, 5], costing 1 + 1 + 1 = 3 (each 5 is a single coin). The min-only version reports 4 — one operation too many.

Why it teaches the fix. The coin reduction is sound; the error is fixing T = min. A difference that's awkward to make from one base (like 4 = 2+2) can become cheap from a base two lower (6... no — here 5 = one coin). So we should let the target dip slightly below the minimum and take the best. The next approach makes that precise.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

arr = [1, 5, 5], target = min = 1

Array state

target 1

diffs [0, 4, 4] → 0 + 2 + 2 = 4

[0]

[1]

[2]

Current pointerResolved stateNot processed

Final result4 (reveals the min-only bug)

C · Code with teaching comments

Reference implementation previewpublic int equalMinOnly(int[] arr) { int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE; for (int a : arr) { min = Math.min(min, a); max = Math.max(max, a); } int D = max - min; int[] dp = new int[D + 1];Explore the full code

solution.javaJava

Brute Force — Coin DP toward the Minimum Only — reference

4 teaching notes

1
public int equalMinOnly(int[] arr) {
2
    int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
3
    for (int a : arr) { min = Math.min(min, a); max = Math.max(max, a); }
4
    // Largest difference any element must descend when targeting the minimum.
5
    int D = max - min;
6
    int[] dp = new int[D + 1];
7
    int[] coins = {1, 2, 5};
8
    for (int v = 1; v <= D; v++) {
9
        dp[v] = Integer.MAX_VALUE;
10
        for (int c : coins) {
11
            // Standard coin-change transition over {1,2,5}.
12
            if (v - c >= 0 && dp[v - c] != Integer.MAX_VALUE) {
13
                dp[v] = Math.min(dp[v], dp[v - c] + 1);
14
            }
15
        }
16
    }
17
    int total = 0;
18
    // Sum the per-element costs — correct subroutine, wrong fixed target.
19
    for (int a : arr) total += dp[a - min];
20
    return total; // can overcount: target is wrongly pinned to min
21
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.21 lines

D · Why it works and complexityO(n · D) timeO(D) spaceOpen the invariant and proofExplore the proof

The reframing (add-to-all-but-one ≡ subtract-from-one) is the real unlock; the coin-change subroutine is standard. The only remaining degree of freedom is the target, and assuming it equals min(arr) is the single bug that separates a wrong answer from a right one.

ComplexityO(n · D) time, O(D) space — Coin-change DP over each difference up to D = max−min costs O(D) per element to fill the table once (reused), then O(n) lookups → O(n·D) in the naive form, O(D + n) if the table is shared.

E · Edge cases and pitfalls3Believing the target must be min(arr) — the core bug this approach exposes.Explore edge cases

Pitfalls

Believing the target must be min(arr) — the core bug this approach exposes.
Building a fresh DP table per element instead of once over the full range.
Forgetting to allow descending below the minimum at all.

03.2

Approach 2 of 3 · Optimal

Greedy Coins over Three Targets (Optimal)

TimeO(n)SpaceO(1)

The answer they want. Phrase it as 'subtract-from-one → coin change, sweep targets min, min−1, min−2'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Lock in the reframing and the coin-change cost. For a difference d, the minimal {1,2,5} count is d//5 fives, then (d%5)//2 twos, then the rest as ones.

2Hint 2Explore hint

Now let the target slide below the minimum. Try base = min, min−1, min−2 and total the per-element coin costs for each.

3Hint 3Explore hint

Return the smallest of the three totals. You never need to go deeper than min−2 — any larger offset is dominated.

A · Core idea

Combine the correct reduction with the right target search.

Per-element cost in O(1). Because {1,2,5} is canonical, greedy is optimal: to cover a difference d, use d/5 fives, then (d%5)/2 twos, then (d%5)%2 ones. So coins(d) = d/5 + (d%5)/2 + (d%5)%2. No table needed.

Sliding the target. The remaining freedom is the common floor T. Lowering T increases every element's difference by the same amount, but coin costs are not linear in d — crossing a multiple-of-5 boundary can drop the cost. The known-tight result is that the optimum lies within two of the minimum, so we evaluate T ∈ {min, min−1, min−2} and take the cheapest total.

Why only three targets. Decreasing T by 5 adds exactly one coin (one extra 5) to every element — never a saving. Within a window of 5, the only residues worth testing are offsets 0, 1, 2 from the minimum: offset 3 and 4 are equivalent (modulo the +1-per-5 effect) to offsets −2 and −1 of the next-lower multiple, already covered. So three targets exhaust the distinct cost profiles.

Walk-through of the win. On [1,5,5]: T=1 → diffs [0,4,4] → 0+2+2 = 4. T=0 → diffs [1,5,5] → 1+1+1 = 3. T=−1 → diffs [2,6,6] → 1 + 2 + 2 = 5. Minimum is 3, at T = min−1. The formula and the three-target sweep deliver it directly.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

arr = [2, 2, 3, 7]

Array state

T=1

diffs [0,4,4] → 4 ops

[0]

[1]

[2]

Current pointerResolved stateNot processed

Final result2

C · Code with teaching comments

solution.javaJava

Greedy Coins over Three Targets (Optimal) — optimal

4 teaching notes

1
public int equal(int[] arr) {
2
    int min = Integer.MAX_VALUE;
3
    for (int a : arr) min = Math.min(min, a);
4
    int best = Integer.MAX_VALUE;
5
    // Sweep the three candidate targets; deeper offsets never help.
6
    for (int base = min; base >= min - 2; base--) {
7
        int total = 0;
8
        // Total operations to bring every element down to this base.
9
        for (int a : arr) total += coins(a - base);
10
        // Keep the cheapest target seen.
11
        best = Math.min(best, total);
12
    }
13
    return best;
14
}
15
 
16
private int coins(int d) {
17
    // Greedy fives→twos→ones — optimal for the canonical set {1,2,5}.
18
    return d / 5 + (d % 5) / 2 + (d % 5) % 2;
19
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.19 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

Coin cost over {1,2,5} is piecewise — it jumps at multiples of 5. Sliding the target shifts every difference together, so the cheapest profile is found within a 3-wide window below the minimum. Three evaluations of an O(1) formula nail the optimum.

ComplexityO(n) time, O(1) space — Three candidate targets × one pass of n elements × O(1) coin formula each → O(n) time and O(1) extra space.

E · Edge cases and pitfalls7arr = [2, 2, 3, 7] — T=min=2 already optimal: diffs [0,0,1,5] → 2 ops.Explore edge cases

Edge cases handled

arr = [2, 2, 3, 7]T=min=2 already optimal: diffs [0,0,1,5] → 2 ops.
arr = [1, 1, 1]All equal: every difference 0 for T=min → 0 operations.
arr = [1, 5, 5]T=min−1=0 wins with 3 ops; the sub-minimum target is essential.
arr = [0]Single element, already 'equal' → 0 operations.

Pitfalls

Sweeping only the minimum as target — misses min−1/min−2 wins.
Writing coins greedily as ones-before-twos — non-minimal; order must be 5,2,1.
Extending the target sweep below min−2 — wasted work; never improves the answer.

03.3

Approach 3 of 3

Coin-Change DP per Target — Robust Variant

TimeO(n + D)SpaceO(D)

Mention when you're unsure the denomination set is canonical, or to show a greedy-free safety net.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

If you don't want to trust greedy, precompute a coin-change-min table once over the full difference range, then look up costs.

2Hint 2Explore hint

dp[v] = 1 + min(dp[v-1], dp[v-2], dp[v-5]); dp[0] = 0. Build it up to (max − (min−2)).

3Hint 3Explore hint

Still sweep the three targets, but read each per-element cost from dp instead of the formula.

A · Core idea

A defensive version that doesn't rely on greedy being optimal — useful if the denominations were, say, {1, 3, 4} where greedy fails.

Build the table once. Compute dp[v] = minimum coins to make value v from {1,2,5} for every v up to the largest difference you could face, which is max − (min − 2). The recurrence is the standard dp[v] = 1 + min(dp[v−1], dp[v−2], dp[v−5]) with dp[0] = 0.

Reuse across targets. For each target T ∈ {min, min−1, min−2}, total dp[a − T] over all elements. Because differences only shift by 0, 1, or 2, every needed index is within the precomputed range.

Why bother when greedy works here. For {1,2,5} greedy is provably optimal, so this DP gives identical answers — it's strictly slower (O(D) build) but conceptually safer and immune to the canonical-system assumption. In an interview, lead with the greedy formula and mention this as the fallback for arbitrary denominations.

Correctness. Coin-change-min DP is exact, and the three-target sweep is the same as the optimal approach, so the result matches the greedy version on every input.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

arr = [10, 7, 12]

Array state

dp table

dp[0..5] = 0,1,1,2,2,1

[0]

[1]

[2]

[3]

[4]

[5]

Current pointerResolved stateNot processed

Final result3

C · Code with teaching comments

Reference implementation previewpublic int equal(int[] arr) { int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE; for (int a : arr) { min = Math.min(min, a); max = Math.max(max, a); } int D = max - (min - 2); int[] dp = new int[D + 1];Explore the full code

solution.javaJava

Coin-Change DP per Target — Robust Variant — reference

4 teaching notes

1
public int equal(int[] arr) {
2
    int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
3
    for (int a : arr) { min = Math.min(min, a); max = Math.max(max, a); }
4
    // Cover the largest difference reachable at target min−2.
5
    int D = max - (min - 2);
6
    int[] dp = new int[D + 1];
7
    int[] coins = {1, 2, 5};
8
    for (int v = 1; v <= D; v++) {
9
        int best = Integer.MAX_VALUE;
10
        for (int c : coins) {
11
            // Coin-change-min recurrence over {1,2,5}.
12
            if (v - c >= 0) best = Math.min(best, dp[v - c] + 1);
13
        }
14
        dp[v] = best;
15
    }
16
    int answer = Integer.MAX_VALUE;
17
    for (int base = min; base >= min - 2; base--) {
18
        int total = 0;
19
        // Table lookups replace the greedy formula.
20
        for (int a : arr) total += dp[a - base];
21
        // Best of the three targets — identical result to the greedy version.
22
        answer = Math.min(answer, total);
23
    }
24
    return answer;
25
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.25 lines

D · Why it works and complexityO(n + D) timeO(D) spaceOpen the invariant and proofExplore the proof

Decoupling 'how much does difference d cost' (a coin-change DP) from 'which target' (the three-way sweep) makes the solution robust to denomination changes. Swap the table's coin set and the rest of the logic is untouched.

ComplexityO(n + D) time, O(D) space — One DP table of size D = max − (min−2) built in O(D); then 3 targets × n lookups in O(n) → O(n + D) total.

E · Edge cases and pitfalls6arr = [1, 5, 5] — Table-based sweep still finds T=0 optimal at 3 ops.Explore edge cases

Edge cases handled

arr = [1, 5, 5]Table-based sweep still finds T=0 optimal at 3 ops.
all equalD could be small/zero; dp[0]=0 → answer 0.
non-canonical coins (hypothetical)This DP stays correct where the greedy formula would fail.

Pitfalls

Sizing the table to max−min instead of max−(min−2) — out-of-bounds at the min−2 target.
Forgetting dp[0]=0, breaking the recurrence base.
Using this where greedy suffices and D is large — unnecessary O(D) overhead.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int equal(int[] arr) { int min = Integer.MAX_VALUE; for (int a : arr) min = Math.min(min, a); int best = Integer.MAX_VALUE; for (int base = min; base >= min - 2; base--) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Pinning the target to the minimum

On [1,5,5], targeting min=1 costs 4 (each 4 = 2+2), but targeting 0 costs 3 (each 5 = one coin). The optimum can sit below the minimum.

Explore the code comparison

Don't write this

m = min(arr)
return sum(coins(a - m) for a in arr)  # only the minimum

Write this instead

m = min(arr)
return min(sum(coins(a - b) for a in arr) for b in (m, m - 1, m - 2))

Non-minimal greedy order

Using ones before twos/fives inflates the count. For d=5, ones-first gives 5 coins; fives-first gives 1.

Explore the code comparison

Don't write this

int ops = d;            // all ones
// ... never uses 2s or 5s

Write this instead

int ops = d / 5 + (d % 5) / 2 + (d % 5) % 2;

Not reframing the operation

Treating 'add to all-but-one' literally invites searching for an ever-growing common value. Recognising it as 'subtract from one' bounds the target near the minimum.

Explore the code comparison

Don't write this

# search increasing targets unboundedly
for T in range(max(arr), max(arr) + BIG):
    ...

Write this instead

# bounded: subtract-from-one, target near the minimum
for base in (min(arr), min(arr) - 1, min(arr) - 2):
    ...

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Reframe add-to-all-but-one as subtract-from-one → per-element coin change over {1,2,5}, scanning 3 candidate targets

Code pattern to memorize

coins(d) = d//5 + (d%5)//2 + (d%5)%2     # min ops to remove d using 5,2,1
m = min(arr)
answer = min over base in {m, m-1, m-2} of
            sum( coins(a - base) for a in arr )

Rules to remember

1Add x to all-but-one ≡ subtract x from one. Absolute values don't matter; only the differences between elements do.
2Reduce each element to a shared target using moves of size 1, 2, 5 — this is exactly minimum coin change on a[i] − target.
3Greedy fives-then-twos-then-ones is optimal for the denomination set {1,2,5} (it's a canonical system), so no DP table is required for the per-element cost.
4The optimal target is not always min(arr) — going to min−1 or min−2 can save coins because a 5 can be cheaper to reach from a lower base. Check min, min−1, min−2.
5You never need to go below min−2: any deeper offset can be replicated more cheaply, so three candidate targets suffice.

Use this pattern when

Operation applies a fixed delta to all-but-one element (or all-but-k) → convert to subtract-from-one
Equalize an array minimizing weighted moves with a fixed set of step sizes
Per-element cost is independent once a global target is chosen
Coin-change-min appears as a subroutine over a small canonical denomination set

Choose another pattern when

Operation targets a single element directly (no all-but-one twist) → plain coin change, no reframing
Denominations aren't canonical (greedy fails) → use coin-change DP per element
You must equalize to a value outside the array with unbounded search → bound the target window first
Operations change differences (e.g. add to a range) → this reduction doesn't apply

Interview takeaway

The whole problem hinges on one reframing: 'add to everyone but one' is just 'subtract from one'. Once you see that, it's minimum coin change per element toward a shared target — and the only trap left is remembering the best target can sit a step or two below the array minimum.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternReframe a confusing batch operation ('add to all-but-one') into its relative dual ('subtract from one'), then recognise the residual as minimum coin change over a small canonical set. The only nuance is the target window: scan min, min−1, min−2. Same coin-change core as Coin Change and Minimum Moves to Equal Array Elements.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Coin Change (Fewest Coins)
The per-element subroutine in isolation — minimum coins to make an amount.
The Coin Change Problem (Count Ways)
Counts combinations instead of minimizing — same denominations, different objective.
Minimum Moves to Equal Array Elements II
Coming soon
Equalize with ±1 moves — the target is the median; contrast the target-choice reasoning.
Array Reduction / Equalize variants
Generalize to other operation sizes — swap the coin set and the three-target window may widen.

Same pattern

←

Construct the Array

Continue · Next problem

Fibonacci Modified

mediumDynamic ProgrammingSometimes asked

Equal

Dynamic Programming · 34 of 44 · 11 min

Karen wants to make all of her colleagues' chocolate counts equal. In a single operation she may add 1, 2, or 5 chocolates to all colleagues except one of her choosing.

Given the initial array of chocolate counts, return the minimum number of operations needed to make every colleague's count equal.

In plain English

Examples

Example 1

Input: arr = [2, 2, 3, 7]
Output: 2
Note: Reframe as lowering to min=2: differences [0,0,1,5]. Removing 1 costs 1 op, removing 5 costs 1 op → 2 operations total. (Equivalently: subtract 1 from the 3, subtract 5 from the 7.)

Example 2

Input: arr = [10, 7, 12]
Output: 3
Note: Target min=7: differences [3,0,5] → coins 2+0+1 = 3. Lower targets are worse here, so 3 is optimal.

Example 3

Input: arr = [1, 5, 5]
Output: 3
Note: Target min=1 gives differences [0,4,4] → 0+2+2 = 4. But target 0 gives [1,5,5] → 1+1+1 = 3. Going one below the minimum saves an operation.

Constraints

1 ≤ n ≤ 10⁴ (number of colleagues)
0 ≤ arr[i] ≤ 1000
Each operation adds exactly 1, 2, or 5 to all-but-one element
Multiple test cases may be batched

Clarifying questions4First question: Why can we treat 'add to all-but-one' as 'subtract from one'?Explore questions

Q1.Why can we treat 'add to all-but-one' as 'subtract from one'?
Adding x to everyone except person p raises the whole group by x and leaves p unchanged — that's the same *relative* outcome as lowering p by x. Since we only care about making counts equal (a relative condition), the two are interchangeable, and subtraction is easier to reason about.
Q2.Does the absolute final value matter?
No, only that all values match. That's why we can freely choose a target and why only the differences between elements drive the cost.
Q3.Why not always target the array minimum?
Because reaching a difference like 3 costs 2 coins (2+1), but if you lower the target by 2, that same element's difference might become 5 (one coin) while others only get slightly more expensive. Net savings are real — hence checking min, min−1, min−2.
Q4.Is greedy coin selection safe with {1, 2, 5}?
Yes. {1,2,5} is a canonical denomination system, so taking as many 5s as possible, then 2s, then 1s is provably minimal. For non-canonical sets you'd need a coin-change DP.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you spot that adding to all-but-one is equivalent to subtracting from one (making only differences matter), and then model the per-element cost as minimum coin change over {1,2,5}.

Where candidates slip

Assuming the target must be the array minimum — missing that min−1 or min−2 can be cheaper — or hand-rolling a wrong greedy that uses ones before twos.

How to stand out

State the subtract-from-one reframing explicitly, justify the greedy {5,2,1} split, and explain why scanning just three targets (min, min−1, min−2) is provably enough.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Coin DP toward the Minimum Only	`O(n · D)`	`O(D)`	Use it to establish the coin-change reduction is correct, then expose the target-selection bug it hides.	Read
2	Greedy Coins over Three Targets (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want. Phrase it as 'subtract-from-one → coin change, sweep targets min, min−1, min−2'.	Read
3	Coin-Change DP per Target — Robust Variant	`O(n + D)`	`O(D)`	Mention when you're unsure the denomination set is canonical, or to show a greedy-free safety net.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.Explore the full tree

From the puzzle to coin change

How to read it:Two reframings turn a confusing operation into a familiar subroutine.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 3

Brute Force — Coin DP toward the Minimum Only

TimeO(n · D)SpaceO(D)

Use it to establish the coin-change reduction is correct, then expose the target-selection bug it hides.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

First nail the reframing: adding to all-but-one is subtracting from one, so target a common value and pay per element to descend to it.

2Hint 2Explore hint

Pick the array minimum as the target and, for each element, compute the minimum number of {1,2,5} moves to cover its difference — a textbook coin-change-min DP.

3Hint 3Explore hint

Now stress-test it on [1,5,5]: targeting the minimum gives 4, but a lower target gives 3. The reduction is right; the fixed target is the flaw.

A · Core idea

Get the modelling right first, then see where the naive choice breaks.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

arr = [1, 5, 5], target = min = 1

Array state

target 1

diffs [0, 4, 4] → 0 + 2 + 2 = 4

[0]

[1]

[2]

Current pointerResolved stateNot processed

Final result4 (reveals the min-only bug)

C · Code with teaching comments

solution.javaJava

Brute Force — Coin DP toward the Minimum Only — reference

4 teaching notes

1
public int equalMinOnly(int[] arr) {
2
    int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
3
    for (int a : arr) { min = Math.min(min, a); max = Math.max(max, a); }
4
    // Largest difference any element must descend when targeting the minimum.
5
    int D = max - min;
6
    int[] dp = new int[D + 1];
7
    int[] coins = {1, 2, 5};
8
    for (int v = 1; v <= D; v++) {
9
        dp[v] = Integer.MAX_VALUE;
10
        for (int c : coins) {
11
            // Standard coin-change transition over {1,2,5}.
12
            if (v - c >= 0 && dp[v - c] != Integer.MAX_VALUE) {
13
                dp[v] = Math.min(dp[v], dp[v - c] + 1);
14
            }
15
        }
16
    }
17
    int total = 0;
18
    // Sum the per-element costs — correct subroutine, wrong fixed target.
19
    for (int a : arr) total += dp[a - min];
20
    return total; // can overcount: target is wrongly pinned to min
21
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.21 lines

D · Why it works and complexityO(n · D) timeO(D) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls3Believing the target must be min(arr) — the core bug this approach exposes.Explore edge cases

Pitfalls

Believing the target must be min(arr) — the core bug this approach exposes.
Building a fresh DP table per element instead of once over the full range.
Forgetting to allow descending below the minimum at all.

03.2

Approach 2 of 3 · Optimal

Greedy Coins over Three Targets (Optimal)

TimeO(n)SpaceO(1)

The answer they want. Phrase it as 'subtract-from-one → coin change, sweep targets min, min−1, min−2'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Lock in the reframing and the coin-change cost. For a difference d, the minimal {1,2,5} count is d//5 fives, then (d%5)//2 twos, then the rest as ones.

2Hint 2Explore hint

Now let the target slide below the minimum. Try base = min, min−1, min−2 and total the per-element coin costs for each.

3Hint 3Explore hint

Return the smallest of the three totals. You never need to go deeper than min−2 — any larger offset is dominated.

A · Core idea

Combine the correct reduction with the right target search.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

arr = [2, 2, 3, 7]

Array state

T=1

diffs [0,4,4] → 4 ops

[0]

[1]

[2]

Current pointerResolved stateNot processed

Final result2

C · Code with teaching comments

solution.javaJava

Greedy Coins over Three Targets (Optimal) — optimal

4 teaching notes

1
public int equal(int[] arr) {
2
    int min = Integer.MAX_VALUE;
3
    for (int a : arr) min = Math.min(min, a);
4
    int best = Integer.MAX_VALUE;
5
    // Sweep the three candidate targets; deeper offsets never help.
6
    for (int base = min; base >= min - 2; base--) {
7
        int total = 0;
8
        // Total operations to bring every element down to this base.
9
        for (int a : arr) total += coins(a - base);
10
        // Keep the cheapest target seen.
11
        best = Math.min(best, total);
12
    }
13
    return best;
14
}
15
 
16
private int coins(int d) {
17
    // Greedy fives→twos→ones — optimal for the canonical set {1,2,5}.
18
    return d / 5 + (d % 5) / 2 + (d % 5) % 2;
19
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.19 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(n) time, O(1) space — Three candidate targets × one pass of n elements × O(1) coin formula each → O(n) time and O(1) extra space.

E · Edge cases and pitfalls7arr = [2, 2, 3, 7] — T=min=2 already optimal: diffs [0,0,1,5] → 2 ops.Explore edge cases

Edge cases handled

arr = [2, 2, 3, 7]T=min=2 already optimal: diffs [0,0,1,5] → 2 ops.
arr = [1, 1, 1]All equal: every difference 0 for T=min → 0 operations.
arr = [1, 5, 5]T=min−1=0 wins with 3 ops; the sub-minimum target is essential.
arr = [0]Single element, already 'equal' → 0 operations.

Pitfalls

Sweeping only the minimum as target — misses min−1/min−2 wins.
Writing coins greedily as ones-before-twos — non-minimal; order must be 5,2,1.
Extending the target sweep below min−2 — wasted work; never improves the answer.

03.3

Approach 3 of 3

Coin-Change DP per Target — Robust Variant

TimeO(n + D)SpaceO(D)

Mention when you're unsure the denomination set is canonical, or to show a greedy-free safety net.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

If you don't want to trust greedy, precompute a coin-change-min table once over the full difference range, then look up costs.

2Hint 2Explore hint

dp[v] = 1 + min(dp[v-1], dp[v-2], dp[v-5]); dp[0] = 0. Build it up to (max − (min−2)).

3Hint 3Explore hint

Still sweep the three targets, but read each per-element cost from dp instead of the formula.

A · Core idea

A defensive version that doesn't rely on greedy being optimal — useful if the denominations were, say, {1, 3, 4} where greedy fails.

Correctness. Coin-change-min DP is exact, and the three-target sweep is the same as the optimal approach, so the result matches the greedy version on every input.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

arr = [10, 7, 12]

Array state

dp table

dp[0..5] = 0,1,1,2,2,1

[0]

[1]

[2]

[3]

[4]

[5]

Current pointerResolved stateNot processed

Final result3

C · Code with teaching comments

solution.javaJava

Coin-Change DP per Target — Robust Variant — reference

4 teaching notes

1
public int equal(int[] arr) {
2
    int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
3
    for (int a : arr) { min = Math.min(min, a); max = Math.max(max, a); }
4
    // Cover the largest difference reachable at target min−2.
5
    int D = max - (min - 2);
6
    int[] dp = new int[D + 1];
7
    int[] coins = {1, 2, 5};
8
    for (int v = 1; v <= D; v++) {
9
        int best = Integer.MAX_VALUE;
10
        for (int c : coins) {
11
            // Coin-change-min recurrence over {1,2,5}.
12
            if (v - c >= 0) best = Math.min(best, dp[v - c] + 1);
13
        }
14
        dp[v] = best;
15
    }
16
    int answer = Integer.MAX_VALUE;
17
    for (int base = min; base >= min - 2; base--) {
18
        int total = 0;
19
        // Table lookups replace the greedy formula.
20
        for (int a : arr) total += dp[a - base];
21
        // Best of the three targets — identical result to the greedy version.
22
        answer = Math.min(answer, total);
23
    }
24
    return answer;
25
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.25 lines

D · Why it works and complexityO(n + D) timeO(D) spaceOpen the invariant and proofExplore the proof

ComplexityO(n + D) time, O(D) space — One DP table of size D = max − (min−2) built in O(D); then 3 targets × n lookups in O(n) → O(n + D) total.

E · Edge cases and pitfalls6arr = [1, 5, 5] — Table-based sweep still finds T=0 optimal at 3 ops.Explore edge cases

Edge cases handled

arr = [1, 5, 5]Table-based sweep still finds T=0 optimal at 3 ops.
all equalD could be small/zero; dp[0]=0 → answer 0.
non-canonical coins (hypothetical)This DP stays correct where the greedy formula would fail.

Pitfalls

Sizing the table to max−min instead of max−(min−2) — out-of-bounds at the min−2 target.
Forgetting dp[0]=0, breaking the recurrence base.
Using this where greedy suffices and D is large — unnecessary O(D) overhead.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Pinning the target to the minimum

On [1,5,5], targeting min=1 costs 4 (each 4 = 2+2), but targeting 0 costs 3 (each 5 = one coin). The optimum can sit below the minimum.

Explore the code comparison

Don't write this

m = min(arr)
return sum(coins(a - m) for a in arr)  # only the minimum

Write this instead

m = min(arr)
return min(sum(coins(a - b) for a in arr) for b in (m, m - 1, m - 2))

Non-minimal greedy order

Using ones before twos/fives inflates the count. For d=5, ones-first gives 5 coins; fives-first gives 1.

Explore the code comparison

Don't write this

int ops = d;            // all ones
// ... never uses 2s or 5s

Write this instead

int ops = d / 5 + (d % 5) / 2 + (d % 5) % 2;

Not reframing the operation

Treating 'add to all-but-one' literally invites searching for an ever-growing common value. Recognising it as 'subtract from one' bounds the target near the minimum.

Explore the code comparison

Don't write this

# search increasing targets unboundedly
for T in range(max(arr), max(arr) + BIG):
    ...

Write this instead

# bounded: subtract-from-one, target near the minimum
for base in (min(arr), min(arr) - 1, min(arr) - 2):
    ...

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Reframe add-to-all-but-one as subtract-from-one → per-element coin change over {1,2,5}, scanning 3 candidate targets

Code pattern to memorize

coins(d) = d//5 + (d%5)//2 + (d%5)%2     # min ops to remove d using 5,2,1
m = min(arr)
answer = min over base in {m, m-1, m-2} of
            sum( coins(a - base) for a in arr )

Rules to remember

1Add x to all-but-one ≡ subtract x from one. Absolute values don't matter; only the differences between elements do.
2Reduce each element to a shared target using moves of size 1, 2, 5 — this is exactly minimum coin change on a[i] − target.
3Greedy fives-then-twos-then-ones is optimal for the denomination set {1,2,5} (it's a canonical system), so no DP table is required for the per-element cost.
4The optimal target is not always min(arr) — going to min−1 or min−2 can save coins because a 5 can be cheaper to reach from a lower base. Check min, min−1, min−2.
5You never need to go below min−2: any deeper offset can be replicated more cheaply, so three candidate targets suffice.

Use this pattern when

Operation applies a fixed delta to all-but-one element (or all-but-k) → convert to subtract-from-one
Equalize an array minimizing weighted moves with a fixed set of step sizes
Per-element cost is independent once a global target is chosen
Coin-change-min appears as a subroutine over a small canonical denomination set

Choose another pattern when

Operation targets a single element directly (no all-but-one twist) → plain coin change, no reframing
Denominations aren't canonical (greedy fails) → use coin-change DP per element
You must equalize to a value outside the array with unbounded search → bound the target window first
Operations change differences (e.g. add to a range) → this reduction doesn't apply

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Coin Change (Fewest Coins)
The per-element subroutine in isolation — minimum coins to make an amount.
The Coin Change Problem (Count Ways)
Counts combinations instead of minimizing — same denominations, different objective.
Minimum Moves to Equal Array Elements II
Coming soon
Equalize with ±1 moves — the target is the median; contrast the target-choice reasoning.
Array Reduction / Equalize variants
Generalize to other operation sizes — swap the coin set and the three-target window may widen.

Same pattern

←

Construct the Array

Continue · Next problem

Fibonacci Modified