Partition 1..N into Two Groups of Minimum Difference

Partition 1..N into Two Groups of Minimum Difference asks you to split the numbers 1, 2, …, n into two groups so that the difference between their sums is as small as possible. It is a clean showcase for greedy balancing: make the locally best choice at each step and the global optimum falls out.

The slow way first

The obvious idea: try every way to split the numbers into two groups, compute each pair of sums, and keep the smallest difference. With n numbers there are 2^n subsets, so this is exponential — hopeless for anything past a few dozen numbers.

The question to ask: do I really need to search? The numbers 1..n are special — they are dense and consecutive. That structure means a simple rule can balance the groups perfectly without any search.

The idea: greedily balance from the top

First note the total: 1 + 2 + … + n = n(n+1)/2. The answer is 0 when that total is even and 1 when it is odd — you can never do better than splitting an odd total into two near-halves.

To actually build the groups, walk the numbers from largest to smallest. For each num, drop it into whichever group currently has the smaller sum. Big numbers are the hardest to place, so we commit them first while there is the most room to correct; the small numbers at the end act as fine-grained filler that closes the gap.

The key insight: always feeding the smaller group keeps the two sums hugging each other, and the ±1 of consecutive numbers lets us land exactly on the best possible split.

Walk through it

Step through the animation. The num pointer scans from the largest cell leftward. Each number lights up, then joins group A or group B depending on which running sum is smaller. By the end A = 8 and B = 7, so the difference is 1 — the minimum for an odd total of 15.

Pseudocode

total = n * (n + 1) / 2                  # sum of 1..n
a, b = 0, 0                              # the two group sums
for num from n down to 1:
    if a <= b:                          # A is the smaller (or tied) group
        a = a + num                     # so grow A
    else:
        b = b + num                     # otherwise grow B
return |a - b|                          # the minimum difference

The Python solution

def min_partition_diff(n):
    total = n * (n + 1) // 2
    a, b = 0, 0
    for num in range(n, 0, -1):
        if a <= b:
            a += num
        else:
            b += num
    return abs(a - b)

• total is computed up front with the closed-form n(n+1)/2 — handy for reasoning, though the loop below is what actually splits the numbers.
• a and b hold the running sums of the two groups, both starting at 0.
• range(n, 0, -1) walks num from n down to 1 — largest first, which is what makes the greedy choice correct.
• Lines 5–9 are the greedy step: if a is the smaller (or tied) sum, the number goes to a; otherwise it goes to b.
• abs(a - b) is the final difference — always 0 for an even total and 1 for an odd one.

Complexity

We keep only two running sums, so the extra space is O(1). The greedy pass replaces an exponential search with a single linear scan — and because the numbers are consecutive, that one pass is provably optimal.

When this pattern shows up

Practice