Description
You are given two integers, n and k.
An array of distinct positive integers is called a k-avoiding array if there does not exist any pair of distinct elements that sum to k.
Return the minimum possible sum of a k-avoiding array of length n.
Example 1:
Input: n = 5, k = 4 Output: 18 Explanation: Consider the k-avoiding array [1,2,4,5,6], which has a sum of 18. It can be proven that there is no k-avoiding array with a sum less than 18.
Example 2:
Input: n = 2, k = 6 Output: 3 Explanation: We can construct the array [1,2], which has a sum of 3. It can be proven that there is no k-avoiding array with a sum less than 3.
Constraints:
1 <= n, k <= 50
Solution
Python3
class Solution:
def minimumSum(self, n: int, k: int) -> int:
seen = set()
res = 0
x = 1
for _ in range(n):
while x < k and k - x in seen:
x += 1
res += x
seen.add(x)
x += 1
return res