Welcome to Subscribe On Youtube
2829. Determine the Minimum Sum of a k-avoiding Array
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
Solutions
Solution 1: Greedy + Simulation
We start from the positive integer $i=1$, and judge whether $i$ can be added to the array in turn. If it can be added, we add $i$ to the array, accumulate it to the answer, and then mark $k-i$ as visited, indicating that $k-i$ cannot be added to the array. The loop continues until the length of the array is $n$.
The time complexity is $O(n^2)$, and the space complexity is $O(n^2)$. Here, $n$ is the length of the array.
-
class Solution { public int minimumSum(int n, int k) { int s = 0, i = 1; boolean[] vis = new boolean[k + n * n + 1]; while (n-- > 0) { while (vis[i]) { ++i; } vis[i] = true; if (k >= i) { vis[k - i] = true; } s += i; } return s; } } -
class Solution { public: int minimumSum(int n, int k) { int s = 0, i = 1; bool vis[k + n * n + 1]; memset(vis, false, sizeof(vis)); while (n--) { while (vis[i]) { ++i; } vis[i] = true; if (k >= i) { vis[k - i] = true; } s += i; } return s; } }; -
class Solution: def minimumSum(self, n: int, k: int) -> int: s, i = 0, 1 vis = set() for _ in range(n): while i in vis: i += 1 vis.add(i) vis.add(k - i) s += i return s -
func minimumSum(n int, k int) int { s, i := 0, 1 vis := make([]bool, k+n*n+1) for ; n > 0; n-- { for vis[i] { i++ } vis[i] = true if k >= i { vis[k-i] = true } s += i } return s } -
function minimumSum(n: number, k: number): number { let s = 0; let i = 1; const vis: boolean[] = Array(n * n + k + 1); while (n--) { while (vis[i]) { ++i; } vis[i] = true; if (k >= i) { vis[k - i] = true; } s += i; } return s; }