Determine the Minimum Sum of a k-avoiding Array

Problem

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 _theminimum possible sum of a k-avoiding array of length _n.

Examples

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

Method 1 – Greedy Construction with Skipping Complements

Intuition

To minimize the sum, we want the smallest possible distinct positive integers. But for a k-avoiding array, we must avoid picking any two numbers that sum to k. This means, for any number x, we cannot pick k-x if x is already picked. The greedy way is to pick numbers from 1 upwards, skipping any number that is the complement of a previously picked number.

Approach

1. Initialize an empty set to keep track of picked numbers.
2. Start from 1 and try to pick the next smallest number.
3. For each candidate x, if k-x is not already picked, add x to the array and the set.
4. Repeat until n numbers are picked.
5. Return the sum of the picked numbers.

Code

C++

class Solution {
public:
    int minimumSum(int n, int k) {
        unordered_set<int> used;
        int ans = 0, x = 1, cnt = 0;
        while (cnt < n) {
            if (!used.count(k - x)) {
                ans += x;
                used.insert(x);
                ++cnt;
            }
            ++x;
        }
        return ans;
    }
};

Go

func minimumSum(n int, k int) int {
    used := map[int]bool{}
    ans, x, cnt := 0, 1, 0
    for cnt < n {
        if !used[k-x] {
            ans += x
            used[x] = true
            cnt++
        }
        x++
    }
    return ans
}

Java

class Solution {
    public int minimumSum(int n, int k) {
        Set<Integer> used = new HashSet<>();
        int ans = 0, x = 1, cnt = 0;
        while (cnt < n) {
            if (!used.contains(k - x)) {
                ans += x;
                used.add(x);
                cnt++;
            }
            x++;
        }
        return ans;
    }
}

Kotlin

class Solution {
    fun minimumSum(n: Int, k: Int): Int {
        val used = mutableSetOf<Int>()
        var ans = 0
        var x = 1
        var cnt = 0
        while (cnt < n) {
            if ((k - x) !in used) {
                ans += x
                used.add(x)
                cnt++
            }
            x++
        }
        return ans
    }
}

Python

class Solution:
    def minimumSum(self, n: int, k: int) -> int:
        used = set()
        ans = 0
        x = 1
        cnt = 0
        while cnt < n:
            if k - x not in used:
                ans += x
                used.add(x)
                cnt += 1
            x += 1
        return ans

Rust

impl Solution {
    pub fn minimum_sum(n: i32, k: i32) -> i32 {
        use std::collections::HashSet;
        let mut used = HashSet::new();
        let mut ans = 0;
        let mut x = 1;
        let mut cnt = 0;
        while cnt < n {
            if !used.contains(&(k - x)) {
                ans += x;
                used.insert(x);
                cnt += 1;
            }
            x += 1;
        }
        ans
    }
}

TypeScript

class Solution {
    minimumSum(n: number, k: number): number {
        const used = new Set<number>();
        let ans = 0, x = 1, cnt = 0;
        while (cnt < n) {
            if (!used.has(k - x)) {
                ans += x;
                used.add(x);
                cnt++;
            }
            x++;
        }
        return ans;
    }
}

Complexity

• ⏰ Time complexity: O(n), since we pick n numbers, and set operations are O(1) on average.
• 🧺 Space complexity: O(n), for storing the used numbers.