---
# System prepended metadata

title: 2829. Determine the Minimum Sum of a k-avoiding Array
tags: [Leetcode, Medium, Math, Greedy]

---

Link: https://leetcode.com/problems/determine-the-minimum-sum-of-a-k-avoiding-array/
## 思路
$O(N)$ $O(N)$ is very intuitive
let's talk about $O(N)$ $O(1)$ in which we don't store all the chosen numbers
The key is, if we find a pair, we replace the larger one with ```n+1``` or ```k```(if ```k``` is bigger)
This way, the substitute will not form a pair with any of the existing elements.
For the next pair, we would use n + 2 (or k + 1), and so on.
The reason why we check ```k-i<=n``` is that we don't need to find a substitute for ```k-i```, if it's larger than ```n```
We only need to find a substitute or directly use all the number between ```[1, n]```
## Code
$O(N)$ $O(1)$
```python=
class Solution:
    def minimumSum(self, n: int, k: int) -> int:
        ans = 0
        last = max(n+1, k)
        for i in range(1, n+1):
            ans += i
            if k-i>i and k-i<=n:
                ans += last-(k-i)
                last += 1
        return ans

```
$O(N)$ $O(N)$
```python=
class Solution:
    def minimumSum(self, n: int, k: int) -> int:
        nums = set()
        ans = 0
        i = 1
        while len(nums)<n:
            if k-i not in nums:
                nums.add(i)
                ans += i
            i += 1
        return ans
```