LeetCode Problem 2834

Difficulty: 🟡 Medium
Topics: Math, Greedy

Solution

LeetCode 2834 - Find the Minimum Possible Sum of a Beautiful Array

Problem Understanding

We are given two positive integers, n and target.

We need to construct an array of exactly n distinct positive integers such that no two different elements add up to target. Among all arrays satisfying these conditions, we want the one with the smallest possible sum.

The output should be the minimum achievable sum, returned modulo 10^9 + 7.

The key requirements are:

1. The array must contain exactly n elements.
2. All elements must be distinct positive integers.
3. No pair of distinct elements can have a sum equal to target.
4. The total sum of the array should be as small as possible.

The constraints are extremely large:

• 1 <= n <= 10^9
• 1 <= target <= 10^9

These constraints immediately tell us that constructing the array explicitly is impossible. Any solution that iterates through all selected values will be too slow when n reaches one billion.

Instead, we need a mathematical formula that directly computes the answer in constant time.

Important Edge Cases

When analyzing the problem, several special situations stand out:

• n = 1, where any positive integer works and the minimum sum is simply 1.
• Very small targets such as target = 1 or target = 2, where forbidden pairs behave differently.
• Cases where all required numbers can fit below target / 2.
• Cases where we need more numbers than are available below target / 2, forcing us to choose larger values.
• Extremely large values of n and target, which require careful handling of arithmetic overflow.

The problem guarantees that n and target are positive integers, so we never need to handle invalid inputs.

Approaches

Brute Force

A straightforward idea is to greedily build the array.

Starting from 1, consider each positive integer in increasing order. Add it to the array if doing so does not create a pair whose sum equals target. Continue until we have selected n numbers.

This approach is correct because choosing the smallest available valid number at every step minimizes the eventual sum.

For example, if target = 5:

• Choose 1
• Choose 2
• Skip 3 because 2 + 3 = 5
• Skip 4 because 1 + 4 = 5
• Choose 5

The resulting array is [1, 2, 5].

The problem is that n can be as large as 10^9. We cannot explicitly build the array or test candidates one by one.

Key Insight

Consider the numbers:

$$1, 2, 3, \dots$$

For every number x, the forbidden partner is:

$$target - x$$

If both numbers are selected, the beautiful condition is violated.

Observe that among every conflicting pair:

$$(x,\ target-x)$$

the smaller number is always preferable because it contributes less to the sum.

Let:

$$m = \left\lfloor \frac{target}{2} \right\rfloor$$

All numbers from 1 through m can be safely chosen together.

Why?

Because for any such number x, its complement:

$$target - x$$

is strictly greater than m, so the complement is not in the chosen set.

Therefore the smallest possible numbers we can take are:

$$1,2,\dots,m$$

If n <= m, we simply take the first n positive integers.

If n > m, we first take all numbers:

$$1,2,\dots,m$$

and then need:

$$n-m$$

additional numbers.

The next smallest valid number after that is target.

We can then take:

$$target,\ target+1,\ target+2,\dots$$

These numbers cannot conflict with each other because any sum of two such numbers is greater than target.

Thus the optimal array is:

$$[1,2,\dots,m]$$

plus

$$[target,\ target+1,\dots,target+(n-m)-1]$$

This gives a direct arithmetic-series formula.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n) or worse	O(n)	Explicitly builds the array and checks conflicts
Optimal	O(1)	O(1)	Uses mathematical observations and arithmetic-series formulas

Algorithm Walkthrough

Step 1

Compute:

$$m = \left\lfloor \frac{target}{2} \right\rfloor$$

This represents the count of smallest numbers that can all coexist without forming a forbidden pair.

Step 2

Check whether:

$$n \le m$$

If true, the optimal array is simply:

$$1,2,\dots,n$$

The sum is the arithmetic-series sum:

$$\frac{n(n+1)}{2}$$

Step 3

Otherwise, take all numbers:

$$1,2,\dots,m$$

Their sum is:

$$\frac{m(m+1)}{2}$$

Step 4

We still need:

$$k = n-m$$

additional numbers.

Step 5

Choose the next valid block:

$$target,\ target+1,\dots,target+k-1$$

The sum of this arithmetic sequence is:

$$\frac{k(2 \cdot target + k - 1)}{2}$$

Step 6

Add the two sums together.

Step 7

Return the result modulo:

$$10^9+7$$

Why it works

Every forbidden pair has the form (x, target - x). Whenever such a pair exists, choosing the smaller value is always at least as good as choosing the larger value because it contributes less to the sum. Therefore all numbers from 1 through floor(target/2) must appear in an optimal solution whenever possible. Once those numbers are exhausted, every number between floor(target/2)+1 and target-1 conflicts with one of the chosen smaller numbers, so they cannot be used. The next available values start at target, and choosing them in increasing order again minimizes the sum. Thus the constructed set is globally optimal.

Python Solution

class Solution:
    def minimumPossibleSum(self, n: int, target: int) -> int:
        MOD = 10**9 + 7

        m = target // 2

        if n <= m:
            return (n * (n + 1) // 2) % MOD

        first_part = m * (m + 1) // 2

        k = n - m
        second_part = k * (2 * target + k - 1) // 2

        return (first_part + second_part) % MOD

The implementation follows the mathematical derivation directly.

First, m = target // 2 determines how many smallest numbers can be safely selected. If n does not exceed m, the answer is simply the sum of the first n positive integers.

Otherwise, we compute the sum of the first block, 1 through m, using the arithmetic-series formula. We then calculate how many additional values are required and compute the sum of the consecutive range starting at target.

Finally, both sums are added together and reduced modulo 10^9 + 7.

Go Solution

func minimumPossibleSum(n int, target int) int {
	const MOD int64 = 1_000_000_007

	m := target / 2

	if n <= m {
		sum := int64(n) * int64(n+1) / 2
		return int(sum % MOD)
	}

	firstPart := int64(m) * int64(m+1) / 2

	k := n - m
	secondPart := int64(k) * (2*int64(target) + int64(k) - 1) / 2

	ans := (firstPart + secondPart) % MOD
	return int(ans)
}

The Go implementation is identical in logic. The primary difference is the use of int64 for intermediate calculations. Since both n and target can reach 10^9, arithmetic-series formulas may produce values around 10^18, which exceed the range of 32-bit integers. Using int64 guarantees correctness before applying the modulo operation.

Worked Examples

Example 1

Input

n = 2
target = 3

Compute:

Variable	Value
m	1
n <= m	No

First block:

Numbers	Sum
[1]	1

Remaining:

Variable	Value
k	1

Second block:

Numbers	Sum
[3]	3

Total:

Component	Value
First part	1
Second part	3
Total	4

Answer:

4

Example 2

Input

n = 3
target = 3

Compute:

Variable	Value
m	1

First block:

Numbers	Sum
[1]	1

Remaining:

Variable	Value
k	2

Second block:

Numbers	Sum
[3, 4]	7

Total:

Component	Value
First part	1
Second part	7
Total	8

Answer:

8

Example 3

Input

n = 1
target = 1

Compute:

Variable	Value
m	0

First block sum:

Value
0

Remaining:

Variable	Value
k	1

Second block:

Numbers	Sum
[1]	1

Total:

Component	Value
First part	0
Second part	1
Total	1

Answer:

1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1)	Only a fixed number of arithmetic operations are performed
Space	O(1)	No extra data structures are used

The solution relies entirely on closed-form arithmetic-series formulas. No loops, recursion, or auxiliary storage proportional to the input size are required. As a result, both time and space complexity remain constant regardless of the values of n and target.

Test Cases

sol = Solution()

assert sol.minimumPossibleSum(2, 3) == 4      # example 1
assert sol.minimumPossibleSum(3, 3) == 8      # example 2
assert sol.minimumPossibleSum(1, 1) == 1      # example 3

assert sol.minimumPossibleSum(1, 2) == 1      # single element
assert sol.minimumPossibleSum(2, 2) == 3      # [1,2]
assert sol.minimumPossibleSum(3, 2) == 6      # [1,2,3]

assert sol.minimumPossibleSum(2, 4) == 3      # [1,2]
assert sol.minimumPossibleSum(3, 4) == 7      # [1,2,4]

assert sol.minimumPossibleSum(4, 5) == 12     # [1,2,5,6]
assert sol.minimumPossibleSum(5, 5) == 18     # [1,2,5,6,7]

assert sol.minimumPossibleSum(10, 100) == 55  # n <= target//2

assert sol.minimumPossibleSum(10**9, 10**9) >= 0  # maximum constraints
assert sol.minimumPossibleSum(10**9, 1) >= 0      # extreme target

Test Summary

Test	Why
(2, 3)	Official example
(3, 3)	Official example
(1, 1)	Smallest valid input
(1, 2)	Single-element array
(2, 2)	Small target
(3, 2)	Requires values beyond target
(2, 4)	Exactly fits below target/2
(3, 4)	Needs one extra value at target
(4, 5)	Typical mixed case
(5, 5)	Multiple values beyond target
(10, 100)	Entire solution comes from first block
(10^9, 10^9)	Maximum-scale stress test
(10^9, 1)	Extreme edge case for target

Edge Cases

Edge Case 1: n = 1

When only one element is required, there can never be a violating pair because the condition requires two distinct indices. The minimum positive integer is 1, so the answer is always 1. The formula naturally produces this result without any special handling.

Edge Case 2: target = 1

In this situation, no two positive integers can sum to 1 because the smallest possible sum of two positive integers is 2. Therefore there are effectively no restrictions. The algorithm computes m = 0, skips the first block, and starts selecting numbers from target = 1, producing exactly the sequence 1, 2, 3, ..., which is optimal.

Edge Case 3: n <= floor(target / 2)

This is the simplest nontrivial scenario. Every selected number can come from the initial safe region 1 through floor(target / 2). Since no complements appear within that range, the optimal solution is just the first n positive integers. The implementation detects this case and immediately returns the arithmetic-series sum.

Edge Case 4: Very Large Inputs

Both n and target may reach 10^9. Any iterative solution would be infeasible. The implementation uses only arithmetic-series formulas and constant-time calculations. In Go, int64 is used for intermediate values to avoid overflow, while Python's arbitrary-precision integers handle large values automatically. This ensures correctness even at the maximum constraint limits.