Skip to content

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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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;
}

Comments