Maximum Composite Numbers Summing to N is a classic greedy number-theory puzzle. You are given an integer N and asked for the largest count of composite numbers (non-primes greater than 1: 4, 6, 8, 9, 10, …) that add up to exactly N. The trick is realizing that "use the most numbers" means "use the smallest building block as often as possible."
Problem. Given an integer N, split it into a sum of composite numbers using as many terms as
possible, and return that maximum count (or -1 if no such split exists).
Example: N = 14 → 4 + 4 + 6 uses 3 composites, the most achievable, so the answer is 3.
The slow way first
The brute-force instinct is to try every combination of composites that sums to N and keep the one with the most terms — a recursive search or a coin-change-style DP over the composites {4, 6, 8, 9, …}. That works, but exploring all combinations is exponential, and even the DP version is heavier than the problem needs.
The question to ask: to use the most numbers, what should each number look like? As small as possible. The smallest composite is 4, so a sum made almost entirely of 4s packs in the most terms.
The idea: pack 4s, then patch the remainder
Take count = N // 4 fours. They sum to a multiple of 4, leaving a remainder r = N % 4. That leftover r (which is 0, 1, 2, or 3) is too small to be its own composite, so we patch it by reshaping a few of the 4s:
The patches all reuse just two extra composites, 6 and 9:
r == 1: trade two 4s for one 9 (since8 + 1 = 9). Count drops by one.r == 2: turn one 4 into a 6 (since4 + 2 = 6). Count is unchanged.r == 3: trade three 4s for a 6 and a 9 (since12 + 3 = 6 + 9). Count drops by one.
Walk through it
Step through the animation with N = 14. We place three 4s (sum 12), see a remainder of 2, and turn the last 4 into a 6. The result 4 + 4 + 6 = 14 uses 3 composites — the maximum.
Pseudocode
count = N // 4 # greedily use as many 4s as possible
r = N % 4 # the leftover
if r == 1: count -= 1 # 8 + 1 = 9 (two 4s -> one 9)
elif r == 2: pass # 4 + 2 = 6 (one 4 -> one 6), count unchanged
elif r == 3: count -= 1 # 12 + 3 = 6 + 9 (three 4s -> a 6 and a 9)
if count <= 0: return -1 # too small to form any composite sum
return countThe Python solution
def max_composites(n):
# smallest composite is 4 -> use as many as possible
count = n // 4
r = n % 4
if r == 1: # 8 + 1 = 9: drop two 4s, add one 9
count -= 1
elif r == 2: # 4 + 2 = 6: turn one 4 into a 6
count = count
elif r == 3: # 12 + 3 = 6 + 9: drop three 4s, add 6 and 9
count -= 1
if count <= 0:
return -1
return countcount = n // 4is the greedy core: assume everything is a 4, the smallest composite.r = n % 4is what those 4s could not cover.- For
r == 1, no single composite ends in…1cheaply, so we borrow from two 4s and spend a 9; the count falls by one. - For
r == 2, a 6 absorbs the leftover for free — one 4 simply becomes a 6, so the count holds. - For
r == 3, we reshape three 4s into a 6 and a 9, again losing one term. - The final
count <= 0guard catches tinyN(like 1, 2, 3, 5, 7) that cannot be written as any composite sum.
Complexity
| Case | Time | Notes |
|---|---|---|
| Brute force / DP over composites | O(N) (moderate) | coin-change style table |
| Greedy (this solution) | O(1) (fast) | just N // 4 and a remainder check |
O(1) (fast)Because the structure of the answer is fully determined by N % 4, the whole thing collapses to a couple of arithmetic operations — no loop, no table.
When this pattern shows up
When a problem asks for the maximum count of pieces summing to a target, greedily favor the smallest valid piece, then handle the few leftover cases by hand. The same move powers "minimum coins" (use the largest coin), "maximum segments," and many tiling puzzles — the optimum is decided by a small remainder modulo the smallest piece.
Do not forget the impossible cases. Small or awkward N (1, 2, 3, 5, 7, and 11) cannot be expressed as a
sum of composites at all, so the guard that returns -1 is essential — a pure N // 4 would wrongly
report a positive count.
Practice
For N = 14, after taking three 4s you have a remainder of 2. Which composite patches it, and what happens to the count?
1. Why does the greedy solution prefer the composite 4?
2. When N % 4 == 2, how is the remainder patched?
3. What is the time complexity of the greedy solution?
4. Why is the count <= 0 check necessary?