Skip to main content
Talentd

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

MediumMathGreedy10 min readAsked at: Infosys
Practice this problem

Problem Statement

You are given positive integers n and target.

An array nums is beautiful if it meets the following conditions:

  • nums.length == n.
  • nums consists of pairwise distinct positive integers.
  • There doesn't exist two distinct indices, i and j, in the range [0, n - 1], such that nums[i] + nums[j] == target.

Return the minimum possible sum that a beautiful array could have modulo 109 + 7.

 

Example 1:

Input: n = 2, target = 3
Output: 4
Explanation: We can see that nums = [1,3] is beautiful.
- The array nums has length n = 2.
- The array nums consists of pairwise distinct positive integers.
- There doesn't exist two distinct indices, i and j, with nums[i] + nums[j] == 3.
It can be proven that 4 is the minimum possible sum that a beautiful array could have.

Example 2:

Input: n = 3, target = 3
Output: 8
Explanation: We can see that nums = [1,3,4] is beautiful.
- The array nums has length n = 3.
- The array nums consists of pairwise distinct positive integers.
- There doesn't exist two distinct indices, i and j, with nums[i] + nums[j] == 3.
It can be proven that 8 is the minimum possible sum that a beautiful array could have.

Example 3:

Input: n = 1, target = 1
Output: 1
Explanation: We can see, that nums = [1] is beautiful.

 

Constraints:

  • 1 <= n <= 109
  • 1 <= target <= 109

Approach Overview

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.

Solution

We can greedily construct the array nums starting from x = 1, choosing x each time and excluding target - x.

Let's denote m = \left\lfloor \frac{target}{2} \right\rfloor.

If x <= m, then the numbers we can choose are 1, 2, cdots, n, so the sum of the array is \left\lfloor \frac{(1+n)n}{2} \right\rfloor.

If x > m, then the numbers we can choose are 1, 2, cdots, m, a total of m numbers, and n - m numbers starting from target, so the sum of the array is \left\lfloor \frac{(1+m)m}{2} \right\rfloor + \left\lfloor \frac{(target + target + n - m - 1)(n-m)}{2} \right\rfloor.

Note that we need to take the modulus of 10^9 + 7 for the result.

The time complexity is O(1), and the space complexity is O(1).

Code

PythonJavaC++GoTypeScriptC#

Python

Java

C++

Go

TypeScript

C#

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy Construction with Hash SetO(n)O(n)Good for understanding the constraint and validating the greedy idea step by step
Greedy + Mathematical FormulaO(1)O(1)Optimal approach when you derive the complement pattern around target

Video Solution

Leetcode Weekly contest 360 - Medium - Find the Minimum Possible Sum of a Beautiful Array • Prakhar Agrawal • 1,657 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Find the Minimum Possible Sum of a Beautiful Array easy or hard?
The problem is rated Medium because the constraint initially suggests simulation, but the optimal solution requires recognizing the complement pattern around the target value. Once the mathematical structure is identified, the implementation becomes straightforward.
Find the Minimum Possible Sum of a Beautiful Array Python/Java solution
Most implementations follow the greedy math formula: compute how many safe numbers exist below target/2, sum them, and if needed add a second arithmetic sequence starting from target. This logic translates easily into Python, Java, C++, Go, or C# using simple integer arithmetic.
How to solve Find the Minimum Possible Sum of a Beautiful Array in O(1)?
Compute k = floor((target - 1) / 2), which represents how many smallest numbers can be safely chosen. If n ≤ k, return the sum of the first n integers. If n > k, take numbers from 1..k and then take the remaining (n - k) numbers starting from target. Both segments are arithmetic sequences, so their sums can be calculated in constant time.
What is the best approach for Find the Minimum Possible Sum of a Beautiful Array?
The optimal approach uses a greedy observation combined with a mathematical formula. All numbers smaller than floor((target-1)/2) can be safely chosen because their complements are larger values that are not selected. If more numbers are needed, continue from target upward. Using arithmetic series formulas reduces the solution to O(1) time and O(1) space.
Is Find the Minimum Possible Sum of a Beautiful Array asked at Google/Amazon/Meta?
Problems combining greedy reasoning with mathematical observations are common in interviews at companies like Google, Amazon, and Meta. While this exact problem may not appear verbatim, the pattern of avoiding complementary values and minimizing sums frequently appears in coding interviews.
What data structure is used in Find the Minimum Possible Sum of a Beautiful Array?
The optimized solution does not require any data structure because it relies purely on mathematical calculations. A more straightforward greedy simulation may use a hash set to track chosen numbers and check whether target - x already exists.
What is the time complexity of Find the Minimum Possible Sum of a Beautiful Array?
The optimal solution runs in O(1) time because it directly computes the sum using arithmetic progression formulas instead of iterating through values. A simpler greedy simulation using a hash set runs in O(n) time and O(n) space while selecting numbers one by one.

Ready to solve this problem?

Practice Find the Minimum Possible Sum of a Beautiful Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Two Numbers

Next

Reverse Integer