Algorithms
Medium
2834
3026
Find the Minimum Possible Sum of a Beautiful Array
find-the-minimum-possible-sum-of-a-beautiful-array
"""
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
"""
class Solution:
    def minimumPossibleSum(self, n: int, target: int) -> int:
        
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


Please complete the code below to solve above prblem:
```python
class Solution:
    def minimumPossibleSum(self, n: int, target: int) -> int:
        
```

my_solution = Solution()

test_input = { "n": 2, "target": 3 }
assert my_solution.minimumPossibleSum(**test_input) == 4

test_input = { "n": 3, "target": 3 }
assert my_solution.minimumPossibleSum(**test_input) == 8

test_input = { "n": 1, "target": 1 }
assert my_solution.minimumPossibleSum(**test_input) == 1

test_input = { "n": 16, "target": 6 }
assert my_solution.minimumPossibleSum(**test_input) == 162

test_input = { "n": 16, "target": 32 }
assert my_solution.minimumPossibleSum(**test_input) == 136

test_input = { "n": 13, "target": 50 }
assert my_solution.minimumPossibleSum(**test_input) == 91

test_input = { "n": 36, "target": 21 }
assert my_solution.minimumPossibleSum(**test_input) == 926

test_input = { "n": 40, "target": 17 }
assert my_solution.minimumPossibleSum(**test_input) == 1076

test_input = { "n": 37, "target": 46 }
assert my_solution.minimumPossibleSum(**test_input) == 1011

test_input = { "n": 33, "target": 7 }
assert my_solution.minimumPossibleSum(**test_input) == 651

test_input = { "n": 42, "target": 46 }
assert my_solution.minimumPossibleSum(**test_input) == 1321

test_input = { "n": 46, "target": 29 }
assert my_solution.minimumPossibleSum(**test_input) == 1529

test_input = { "n": 9, "target": 43 }
assert my_solution.minimumPossibleSum(**test_input) == 45

test_input = { "n": 30, "target": 31 }
assert my_solution.minimumPossibleSum(**test_input) == 690

test_input = { "n": 14, "target": 47 }
assert my_solution.minimumPossibleSum(**test_input) == 105

test_input = { "n": 5, "target": 3 }
assert my_solution.minimumPossibleSum(**test_input) == 19

test_input = { "n": 41, "target": 23 }
assert my_solution.minimumPossibleSum(**test_input) == 1191

test_input = { "n": 17, "target": 13 }
assert my_solution.minimumPossibleSum(**test_input) == 219

test_input = { "n": 9, "target": 13 }
assert my_solution.minimumPossibleSum(**test_input) == 63

test_input = { "n": 29, "target": 18 }
assert my_solution.minimumPossibleSum(**test_input) == 595

test_input = { "n": 21, "target": 14 }
assert my_solution.minimumPossibleSum(**test_input) == 315

test_input = { "n": 4, "target": 6 }
assert my_solution.minimumPossibleSum(**test_input) == 12

test_input = { "n": 38, "target": 15 }
assert my_solution.minimumPossibleSum(**test_input) == 958

test_input = { "n": 14, "target": 7 }
assert my_solution.minimumPossibleSum(**test_input) == 138

test_input = { "n": 18, "target": 26 }
assert my_solution.minimumPossibleSum(**test_input) == 231

test_input = { "n": 11, "target": 15 }
assert my_solution.minimumPossibleSum(**test_input) == 94

test_input = { "n": 7, "target": 8 }
assert my_solution.minimumPossibleSum(**test_input) == 37

test_input = { "n": 11, "target": 22 }
assert my_solution.minimumPossibleSum(**test_input) == 66

test_input = { "n": 36, "target": 11 }
assert my_solution.minimumPossibleSum(**test_input) == 821

test_input = { "n": 18, "target": 29 }
assert my_solution.minimumPossibleSum(**test_input) == 227

test_input = { "n": 26, "target": 17 }
assert my_solution.minimumPossibleSum(**test_input) == 495

test_input = { "n": 37, "target": 13 }
assert my_solution.minimumPossibleSum(**test_input) == 889

test_input = { "n": 46, "target": 38 }
assert my_solution.minimumPossibleSum(**test_input) == 1567

test_input = { "n": 13, "target": 7 }
assert my_solution.minimumPossibleSum(**test_input) == 121

test_input = { "n": 33, "target": 34 }
assert my_solution.minimumPossibleSum(**test_input) == 817

test_input = { "n": 39, "target": 12 }
assert my_solution.minimumPossibleSum(**test_input) == 945

test_input = { "n": 1, "target": 45 }
assert my_solution.minimumPossibleSum(**test_input) == 1

test_input = { "n": 37, "target": 36 }
assert my_solution.minimumPossibleSum(**test_input) == 1026

test_input = { "n": 16, "target": 19 }
assert my_solution.minimumPossibleSum(**test_input) == 199

test_input = { "n": 22, "target": 15 }
assert my_solution.minimumPossibleSum(**test_input) == 358

test_input = { "n": 34, "target": 42 }
assert my_solution.minimumPossibleSum(**test_input) == 855

test_input = { "n": 50, "target": 22 }
assert my_solution.minimumPossibleSum(**test_input) == 1665

test_input = { "n": 42, "target": 44 }
assert my_solution.minimumPossibleSum(**test_input) == 1323

test_input = { "n": 40, "target": 8 }
assert my_solution.minimumPossibleSum(**test_input) == 928

test_input = { "n": 7, "target": 19 }
assert my_solution.minimumPossibleSum(**test_input) == 28

test_input = { "n": 44, "target": 10 }
assert my_solution.minimumPossibleSum(**test_input) == 1146

test_input = { "n": 21, "target": 6 }
assert my_solution.minimumPossibleSum(**test_input) == 267

test_input = { "n": 27, "target": 26 }
assert my_solution.minimumPossibleSum(**test_input) == 546

test_input = { "n": 49, "target": 4 }
assert my_solution.minimumPossibleSum(**test_input) == 1272

test_input = { "n": 35, "target": 2 }
assert my_solution.minimumPossibleSum(**test_input) == 630

test_input = { "n": 32, "target": 29 }
assert my_solution.minimumPossibleSum(**test_input) == 780

test_input = { "n": 20, "target": 41 }
assert my_solution.minimumPossibleSum(**test_input) == 210

test_input = { "n": 30, "target": 48 }
assert my_solution.minimumPossibleSum(**test_input) == 603

test_input = { "n": 12, "target": 34 }
assert my_solution.minimumPossibleSum(**test_input) == 78

test_input = { "n": 50, "target": 44 }
assert my_solution.minimumPossibleSum(**test_input) == 1863

test_input = { "n": 42, "target": 26 }
assert my_solution.minimumPossibleSum(**test_input) == 1251

test_input = { "n": 3, "target": 18 }
assert my_solution.minimumPossibleSum(**test_input) == 6

test_input = { "n": 11, "target": 3 }
assert my_solution.minimumPossibleSum(**test_input) == 76

test_input = { "n": 38, "target": 29 }
assert my_solution.minimumPossibleSum(**test_input) == 1077

test_input = { "n": 17, "target": 24 }
assert my_solution.minimumPossibleSum(**test_input) == 208

test_input = { "n": 50, "target": 31 }
assert my_solution.minimumPossibleSum(**test_input) == 1800

test_input = { "n": 32, "target": 41 }
assert my_solution.minimumPossibleSum(**test_input) == 768

test_input = { "n": 12, "target": 24 }
assert my_solution.minimumPossibleSum(**test_input) == 78

test_input = { "n": 35, "target": 43 }
assert my_solution.minimumPossibleSum(**test_input) == 924

test_input = { "n": 9, "target": 47 }
assert my_solution.minimumPossibleSum(**test_input) == 45

test_input = { "n": 32, "target": 26 }
assert my_solution.minimumPossibleSum(**test_input) == 756

test_input = { "n": 6, "target": 42 }
assert my_solution.minimumPossibleSum(**test_input) == 21

test_input = { "n": 11, "target": 1 }
assert my_solution.minimumPossibleSum(**test_input) == 66

test_input = { "n": 11, "target": 24 }
assert my_solution.minimumPossibleSum(**test_input) == 66

test_input = { "n": 39, "target": 38 }
assert my_solution.minimumPossibleSum(**test_input) == 1140

test_input = { "n": 18, "target": 8 }
assert my_solution.minimumPossibleSum(**test_input) == 213

test_input = { "n": 29, "target": 5 }
assert my_solution.minimumPossibleSum(**test_input) == 489

test_input = { "n": 44, "target": 6 }
assert my_solution.minimumPossibleSum(**test_input) == 1072

test_input = { "n": 29, "target": 30 }
assert my_solution.minimumPossibleSum(**test_input) == 631

test_input = { "n": 13, "target": 47 }
assert my_solution.minimumPossibleSum(**test_input) == 91

test_input = { "n": 46, "target": 21 }
assert my_solution.minimumPossibleSum(**test_input) == 1441

test_input = { "n": 46, "target": 6 }
assert my_solution.minimumPossibleSum(**test_input) == 1167

test_input = { "n": 27, "target": 30 }
assert my_solution.minimumPossibleSum(**test_input) == 546

test_input = { "n": 5, "target": 35 }
assert my_solution.minimumPossibleSum(**test_input) == 15

test_input = { "n": 12, "target": 32 }
assert my_solution.minimumPossibleSum(**test_input) == 78

test_input = { "n": 13, "target": 39 }
assert my_solution.minimumPossibleSum(**test_input) == 91

test_input = { "n": 10, "target": 11 }
assert my_solution.minimumPossibleSum(**test_input) == 80

test_input = { "n": 46, "target": 14 }
assert my_solution.minimumPossibleSum(**test_input) == 1315

test_input = { "n": 37, "target": 18 }
assert my_solution.minimumPossibleSum(**test_input) == 927

test_input = { "n": 32, "target": 8 }
assert my_solution.minimumPossibleSum(**test_input) == 612

test_input = { "n": 26, "target": 14 }
assert my_solution.minimumPossibleSum(**test_input) == 465

test_input = { "n": 33, "target": 41 }
assert my_solution.minimumPossibleSum(**test_input) == 821

test_input = { "n": 44, "target": 39 }
assert my_solution.minimumPossibleSum(**test_input) == 1465

test_input = { "n": 3, "target": 21 }
assert my_solution.minimumPossibleSum(**test_input) == 6

test_input = { "n": 9, "target": 11 }
assert my_solution.minimumPossibleSum(**test_input) == 65

test_input = { "n": 16, "target": 43 }
assert my_solution.minimumPossibleSum(**test_input) == 136

test_input = { "n": 7, "target": 22 }
assert my_solution.minimumPossibleSum(**test_input) == 28

test_input = { "n": 21, "target": 49 }
assert my_solution.minimumPossibleSum(**test_input) == 231

test_input = { "n": 23, "target": 16 }
assert my_solution.minimumPossibleSum(**test_input) == 381

test_input = { "n": 33, "target": 32 }
assert my_solution.minimumPossibleSum(**test_input) == 816

test_input = { "n": 22, "target": 1 }
assert my_solution.minimumPossibleSum(**test_input) == 253

test_input = { "n": 5, "target": 47 }
assert my_solution.minimumPossibleSum(**test_input) == 15

test_input = { "n": 38, "target": 7 }
assert my_solution.minimumPossibleSum(**test_input) == 846

test_input = { "n": 38, "target": 24 }
assert my_solution.minimumPossibleSum(**test_input) == 1027

test_input = { "n": 13, "target": 36 }
assert my_solution.minimumPossibleSum(**test_input) == 91