2834. Find the Minimum Possible Sum of a Beautiful Array#
Given two positive integers: and .
If an array satisfies the following conditions, it is called a beautiful array.
- consists of positive integers that are pairwise distinct.
- Within the range , there does not exist two different indices and such that .
Return the minimum sum that a beautiful array satisfying the conditions can have, and take the result modulo .
Example 1:
Input: n = 2, target = 3
Output: 4
Explanation: nums = [1,3] is a beautiful array.
- The length of nums is n = 2.
- nums consists of positive integers that are pairwise distinct.
- There does not exist two different indices i and j such that nums[i] + nums[j] == 3.
It can be proven that 4 is the minimum sum that a beautiful array satisfying the conditions can have.
Example 2:
Input: n = 3, target = 3
Output: 8
Explanation:
nums = [1,3,4] is a beautiful array.
- The length of nums is n = 3.
- nums consists of positive integers that are pairwise distinct.
- There does not exist two different indices i and j such that nums[i] + nums[j] == 3.
It can be proven that 8 is the minimum sum that a beautiful array satisfying the conditions can have.
Example 3:
Input: n = 1, target = 1
Output: 1
Explanation: nums = [1] is a beautiful array.
Constraints:
Greedy#
class Solution {
public:
int minimumPossibleSum(int n, int target) {
const int mod = 1e9 + 7;
int m = target / 2;
if (n <= m) {
return (long long) (1 + n) * n / 2 % mod;
}
return ((long long) (1 + m) * m / 2 +
((long long) target + target + (n - m) - 1) * (n - m) / 2) % mod;
}
};