Find the Minimum Possible Sum of a Beautiful Array - Solution & Explanation

Problem Overview: You need to construct an array of n distinct positive integers such that no two elements sum to target. Among all valid arrays, return the minimum possible sum. The challenge is selecting numbers that avoid forbidden pairs while keeping the total as small as possible.

Approach 1: Greedy Construction with Set (O(n) time, O(n) space)

A direct strategy is to build the array from the smallest positive numbers upward. Maintain a set of chosen values. For each candidate number x, check whether target - x already exists in the set. If it does, adding x would create a forbidden pair that sums to target, so skip it. Otherwise include x and continue until you pick n numbers. This works because picking smaller values first always minimizes the total sum. The set lookup ensures constant‑time validation of the constraint.

This approach demonstrates the greedy idea clearly, but it still iterates through numbers and stores previously chosen values. Time complexity is O(n) and space complexity is O(n). It’s a good starting point to reason about the constraint, especially when learning greedy algorithms.

Approach 2: Greedy + Mathematics Formula (O(1) time, O(1) space)

The key observation is that conflicts only happen between pairs x and target - x. All integers strictly less than target / 2 are safe because their complements are larger numbers that we simply avoid picking. That means the optimal strategy is to take as many numbers as possible from the prefix 1, 2, 3, ... up to floor((target - 1) / 2). Let k = floor((target - 1) / 2). These numbers never conflict with each other.

If n ≤ k, the answer is just the sum of the first n integers. If n > k, take all numbers from 1..k, then continue from target upward for the remaining elements. Starting from target avoids all complements of the earlier numbers. Both segments are simple arithmetic progressions, so you compute their sums using closed‑form formulas. This reduces the algorithm to constant time and constant space using basic math reasoning combined with a greedy selection strategy.

Recommended for interviews: The Greedy + Mathematics approach is what most interviewers expect. It shows you recognize the complement pattern around target and convert the greedy selection into a constant‑time formula. Explaining the set-based greedy version first helps demonstrate understanding, but deriving the mathematical shortcut proves stronger problem‑solving skills.