find-the-minimum-possible-sum-of-a-beautiful-array

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given positive integers <code>n</code> and <code>target</code>.

An array <code>nums</code> is beautiful if it meets the following conditions:

<ul>
	<li><code>nums.length == n</code>.</li>
	<li><code>nums</code> consists of pairwise distinct positive integers.</li>
	<li>There doesn&#39;t exist two distinct indices, <code>i</code> and <code>j</code>, in the range <code>[0, n - 1]</code>, such that <code>nums[i] + nums[j] == target</code>.</li>
</ul>

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

&nbsp;
Example 1:

<pre>
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&#39;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.
</pre>

Example 2:

<pre>
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&#39;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.
</pre>

Example 3:

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

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= n &lt;= 109</code></li>
	<li><code>1 &lt;= target &lt;= 109</code></li>
</ul>

minimumPossibleSum

Find the Minimum Possible Sum of a Beautiful Array

Greedy

Math

给你两个正整数：<code>n</code> 和 <code>target</code> 。

如果数组 <code>nums</code> 满足下述条件，则称其为 美丽数组 。

<ul>
	<li><code>nums.length == n</code>.</li>
	<li><code>nums</code> 由两两互不相同的正整数组成。</li>
	<li>在范围 <code>[0, n-1]</code> 内，不存在 两个 不同 下标 <code>i</code> 和 <code>j</code> ，使得 <code>nums[i] + nums[j] == target</code> 。</li>
</ul>

返回符合条件的美丽数组所可能具备的 最小 和，并对结果进行取模 <code>109&nbsp;+ 7</code>。

&nbsp;

示例 1：

<pre>
输入：n = 2, target = 3
输出：4
解释：nums = [1,3] 是美丽数组。
- nums 的长度为 n = 2 。
- nums 由两两互不相同的正整数组成。
- 不存在两个不同下标 i 和 j ，使得 nums[i] + nums[j] == 3 。
可以证明 4 是符合条件的美丽数组所可能具备的最小和。</pre>

示例 2：

<pre>
输入：n = 3, target = 3
输出：8
解释：
nums = [1,3,4] 是美丽数组。 
- nums 的长度为 n = 3 。 
- nums 由两两互不相同的正整数组成。 
- 不存在两个不同下标 i 和 j ，使得 nums[i] + nums[j] == 3 。
可以证明 8 是符合条件的美丽数组所可能具备的最小和。</pre>

示例 3：

<pre>
输入：n = 1, target = 1
输出：1
解释：nums = [1] 是美丽数组。
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= n &lt;= 109</code></li>
	<li><code>1 &lt;= target &lt;= 109</code></li>
</ul>