LeetCode 2829. Determine the Minimum Sum of a k-avoiding Array Solution in Java, C++, Python & More | Explanation + Code

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

Starting from the positive integer i = 1, we sequentially determine if i can be added to the array. 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. We continue this process until the array's length reaches n.

The time complexity is O(n + k), and the space complexity is O(n + k). Where n is the length of the array.

PythonJavaC++GoTypeScriptRust

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(k - i) s += i i += 1 return s(code-box)

class Solution { public int minimumSum(int n, int k) { int s = 0, i = 1; boolean[] vis = new boolean[n + k + 1]; while (n-- > 0) { while (vis[i]) { ++i; } if (k >= i) { vis[k - i] = true; } s += i++; } return s; } }(code-box)

class Solution { public: int minimumSum(int n, int k) { int s = 0, i = 1; bool vis[n + k + 1]; memset(vis, false, sizeof(vis)); while (n--) { while (vis[i]) { ++i; } if (k >= i) { vis[k - i] = true; } s += i++; } return s; } };(code-box)

func minimumSum(n int, k int) int { s, i := 0, 1 vis := make([]bool, n+k+1) for ; n > 0; n-- { for vis[i] { i++ } if k >= i { vis[k-i] = true } s += i i++ } return s }(code-box)

function minimumSum(n: number, k: number): number { let s = 0; let i = 1; const vis: boolean[] = Array(n + k + 1).fill(false); while (n--) { while (vis[i]) { ++i; } if (k >= i) { vis[k - i] = true; } s += i++; } return s; }(code-box)

impl Solution { pub fn minimum_sum(n: i32, k: i32) -> i32 { let (mut s, mut i) = (0, 1); let mut vis = std::collections::HashSet::new(); for _ in 0..n { while vis.contains(&i) { i += 1; } vis.insert(k - i); s += i; i += 1; } s } }(code-box)