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
andj
, in the range[0, n - 1]
, such thatnums[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 + Mathematics
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)$.
1 2 3 4 5 6 7 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 |
|
1 2 3 4 5 6 7 8 |
|