2829. Determine the Minimum Sum of a k-avoiding Array

Medium60.5% acceptance40,110 / 66,255 submissions

Asked by 1 company

Topics


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

Hints

Hint 1
Try to start with the smallest possible integers.
Hint 2
Check if the current number can be added to the array.
Hint 3
To check if the current number can be added, keep track of already added numbers in a set.
Hint 4
If the number i is added to the array, then i + k can not be added.