# 2834. Find the Minimum Possible Sum of a Beautiful Array

## Description

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

## Solutions

Solution 1: Greedy + Hash Table

We start from the positive integer $i=1$, and judge whether $i$ can be added to the array in turn. If it can be added, we add $i$ to the array, accumulate it to the answer, and then mark $target-i$ as visited, indicating that $target-i$ cannot be added to the array. The loop continues until the length of the array is $n$.

The time complexity is $O(n + target)$, and the space complexity is $O(n + target)$. Here, $n$ is the length of the array.

• 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;
}
}

• 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;
}
};

• 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
i += 1
return ans


• func minimumPossibleSum(n int, target int) (ans int64) {
vis := make([]bool, n+target)
for i := 1; n > 0; i, n = i+1, n-1 {
for vis[i] {
i++
}
ans += int64(i)
if target >= i {
vis[target-i] = true
}
}
return
}

• function minimumPossibleSum(n: number, target: number): number {
const vis: boolean[] = Array(n + target).fill(false);
let ans = 0;
for (let i = 1; n; ++i, --n) {
while (vis[i]) {
++i;
}
ans += i;
if (target >= i) {
vis[target - i] = true;
}
}
return ans;
}


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