# Find the Minimum Possible Sum of a Beautiful Array
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-the-minimum-possible-sum-of-a-beautiful-array)
Canonical: https://scaleengineer.com/dsa/problems/find-the-minimum-possible-sum-of-a-beautiful-array
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Companies:** [Infosys](https://scaleengineer.com/companies/infosys)
---
## Problem
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`

# Approaches
## Greedy Simulation with a Set
This approach directly simulates the process of building the beautiful array. The core idea is to construct the array greedily to ensure the sum is minimized. To do this, we iterate through positive integers starting from 1 and add them to our array if they do not violate the 'beautiful' condition. The condition is that for any two numbers `x` and `y` in the array, `x + y != target`. This means if we add a number `num`, we cannot add `target - num` later. A `HashSet` is used to keep track of the numbers already included in our array for efficient lookups.
**Time:** O(n + target). In the worst-case scenario, the loop might run up to `n + target/2` times to find `n` valid numbers. Given the constraints, this approach is too slow and will time out. · **Space:** O(n). The `HashSet` will store up to `n` elements. Given `n` can be as large as 10<sup>9</sup>, this will lead to a Memory Limit Exceeded error.
**Pros:** The logic is straightforward and easy to understand.; It correctly models the greedy choice of picking the smallest available numbers.
**Cons:** Highly inefficient for large values of `n` and `target` due to its linear time and space complexity relative to `n`.; Will result in a Time Limit Exceeded (TLE) error for the given constraints.; Will result in a Memory Limit Exceeded (MLE) error for the given constraints.
### Explanation
To achieve the minimum possible sum, our strategy should be to select the smallest possible distinct positive integers. We can iterate through integers `num = 1, 2, 3, ...` and decide whether to include them in our array.

A number `num` can be included if, for all existing numbers `x` in our array, `num + x != target`. This is equivalent to checking if `target - num` is already in our array. We can use a `HashSet` to store the numbers we've chosen, allowing for an average O(1) time complexity for this check.

We continue this process, adding the smallest valid integers, until we have collected `n` numbers. The sum is accumulated along the way, with modulo operations to prevent overflow.

```java
import java.util.HashSet;

class Solution {
    public int minimumPossibleSum(int n, int target) {
        HashSet<Integer> seen = new HashSet<>();
        long sum = 0;
        int count = 0;
        int num = 1;
        long MOD = 1_000_000_007;

        while (count < n) {
            if (!seen.contains(target - num)) {
                sum = (sum + num);
                seen.add(num);
                count++;
            }
            num++;
        }
        return (int)(sum % MOD);
    }
}
```
This code snippet implements the greedy strategy. However, since `n` can be up to 10<sup>9</sup>, a loop that depends on `n` will be too slow.
### Algorithm
- Initialize `sum = 0`, `count = 0`, `num = 1`, and a `HashSet` named `seen`.
- Loop until `n` numbers are found (i.e., `count == n`).
- In each iteration, check if `target - num` is already present in the `seen` set.
- If it is not present, it means adding `num` will not violate the beautiful array condition. So, add `num` to the `sum` and to the `seen` set, and then increment `count`.
- Increment `num` in every iteration to consider the next integer.
- After the loop finishes, return the total `sum`.

## Mathematical Approach using Arithmetic Progression
By analyzing the greedy strategy from the first approach, we can observe a distinct pattern in the numbers that are selected. This pattern allows us to derive a direct mathematical formula to compute the sum without any iteration, leading to a highly efficient O(1) solution. This approach is necessary to pass the large constraints of the problem.
**Time:** O(1). The sum is calculated using a direct mathematical formula involving a few arithmetic operations, which take constant time. · **Space:** O(1). The solution uses only a few variables for calculation, irrespective of the input size.
**Pros:** Extremely efficient, with constant time and space complexity.; Handles the large constraints on `n` and `target` effectively.; Provides a direct and elegant solution once the pattern is understood.
**Cons:** The derivation of the formula requires mathematical insight into the pattern, which might not be immediately obvious.
### Explanation
The greedy strategy of picking the smallest available positive integer `i` as long as `target - i` is not already in our set leads to a predictable sequence of numbers.

- For any integer `i <= target / 2`, its counterpart `j = target - i` is greater than or equal to `i`. Since we pick numbers in increasing order, when we consider `i`, `j` has not been considered yet, so we will always pick `i`. This means we select all integers from `1` to `m = floor(target / 2)`.

- For any integer `i` such that `target / 2 < i < target`, its counterpart `j = target - i` is smaller than `i` (i.e., `j <= m`). Since we have already picked all numbers up to `m`, `j` is already in our set. Therefore, we must skip all such `i`.

- For any integer `i >= target`, its counterpart `target - i` is not a positive integer, so it cannot be in our set of chosen positive integers. Thus, we can pick any `i >= target`.

This means the set of available numbers for our beautiful array is `{1, 2, ..., m} 	cup {target, target+1, ...}`. To get the minimum sum, we take the `n` smallest numbers from this combined set.

This leads to two cases:
1.  **`n <= m`**: We just need the first `n` numbers, which are `1, 2, ..., n`. The sum is `n * (n + 1) / 2`.
2.  **`n > m`**: We take all `m` numbers from `1` to `m`, and then we need `k = n - m` more numbers. The next smallest available numbers are `target, target + 1, ...`. We take the first `k` numbers from this sequence. The total sum is the sum of these two arithmetic progressions.

This logic can be implemented with constant time complexity.

```java
class Solution {
    public int minimumPossibleSum(int n, int target) {
        long MOD = 1_000_000_007;
        long m = target / 2;

        if (n <= m) {
            long val = n;
            long sum = val * (val + 1) / 2;
            return (int) (sum % MOD);
        } else {
            // Sum of the first part: 1, 2, ..., m
            long sum1 = m * (m + 1) / 2;

            // Sum of the second part: k = n - m numbers starting from target
            long k = n - m;
            // Arithmetic series: k*a + k*(k-1)/2
            long sum2 = k * target + k * (k - 1) / 2;

            long totalSum = (sum1 % MOD + sum2 % MOD) % MOD;
            return (int) totalSum;
        }
    }
}
```
### Algorithm
- Calculate `m = target / 2`.
- **Case 1: `n <= m`**
  - The array will consist of the first `n` positive integers: `1, 2, ..., n`.
  - The sum is the sum of the first `n` natural numbers: `sum = n * (n + 1) / 2`.
- **Case 2: `n > m`**
  - The array is formed by two groups of numbers:
    1. The first `m` positive integers: `1, 2, ..., m`.
    2. The next `n - m` numbers, starting from `target`: `target, target + 1, ...`.
  - Calculate the sum of the first part: `sum1 = m * (m + 1) / 2`.
  - Calculate the sum of the second part, which is an arithmetic series of `k = n - m` terms: `sum2 = k * target + k * (k - 1) / 2`.
  - The total sum is `(sum1 % MOD + sum2 % MOD) % MOD`.
- Use `long` for all intermediate calculations to prevent integer overflow.

# Solutions
### CSharp

```csharp
public class Solution {
    public int MinimumPossibleSum(int n, int target) {
        const int mod = (int) 1 e9 + 7;
        int m = target / 2;
        if (n <= m) {
            return (int)((1 L + n) * n / 2 % mod);
        }
        long a = (1 L + m) * m / 2 % mod;
        long b = ((1 L * target + target + n - m - 1) * (n - m) / 2) % mod;
        return (int)((a + b) % mod);
    }
}
```

### Java

```java
class Solution {
public
  long minimumPossibleSum(int n, int target) {
    boolean[] vis = new boolean[n + target];
    long ans = 0;
    for (int i = 1; n > 0; --n, ++i) {
      while (vis[i]) {
        ++i;
      }
      ans += i;
      if (target >= i) {
        vis[target - i] = true;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long minimumPossibleSum(int n, int target) {
    bool vis[n + target];
    memset(vis, false, sizeof(vis));
    long long ans = 0;
    for (int i = 1; n; ++i, --n) {
      while (vis[i]) {
        ++i;
      }
      ans += i;
      if (target >= i) {
        vis[target - i] = true;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def minimumPossibleSum(self, n: int, target: int) -> int: vis = set() ans = 0 i = 1 for _ in range(n): while i in vis: i += 1 ans += i vis . add(target - i) i += 1 return ans

```