# Determine the Minimum Sum of a k-avoiding Array
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/determine-the-minimum-sum-of-a-k-avoiding-array)
Canonical: https://scaleengineer.com/dsa/problems/determine-the-minimum-sum-of-a-k-avoiding-array
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Companies:** [Infosys](https://scaleengineer.com/companies/infosys)
---
## 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 _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`

# Approaches
## Greedy Simulation with a Set
This approach greedily builds the k-avoiding array by iterating through positive integers `1, 2, 3, ...` and adding an integer `num` to our array if it doesn't violate the k-avoiding condition. To do this efficiently, we maintain a set of the numbers already added to the array. For each candidate number `num`, we check if `k - num` is already in the set. If it's not, we add `num` to the set and to our total sum. We repeat this process until the array has `n` elements.
**Time:** O(n + k). In the worst-case scenario, to find `n` numbers, we might have to iterate up to `num` being roughly `n + k/2`. For example, if `k` is small, we skip many numbers. Since `n, k <= 50`, the number of iterations is small. Each iteration involves a hash set operation, which is O(1) on average. · **Space:** O(n). The `HashSet` stores at most `n` elements that are added to the k-avoiding array.
**Pros:** Simple to understand and implement as it directly simulates the greedy decision-making process.; Correct and works for the given constraints.
**Cons:** Slightly less efficient than a purely mathematical approach.; Uses extra space to store the seen numbers.
### Explanation
To find the minimum sum, we should always try to include the smallest possible positive integers. This suggests a greedy strategy.

We iterate through integers starting from 1. Let's call the current integer `num`.

We maintain a `HashSet` to store the elements we've chosen for our array. This allows for quick O(1) average time lookups.

For each `num`, we check if adding it would violate the condition. An element `x` violates the condition if there's already an element `y` in our set such that `x + y = k`. So, for our candidate `num`, we check if `k - num` exists in the `HashSet`.

If `k - num` is not in the set, it's safe to add `num`. We add it to the set, add its value to the running sum, and increment the count of elements we've found.

If `k - num` is in the set, we must skip `num` and try the next integer, `num + 1`.

We continue this process until we have collected `n` numbers.

Here is a code snippet demonstrating the logic:
```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public long minimumSum(int n, int k) {
        Set<Integer> seen = new HashSet<>();
        long sum = 0;
        int count = 0;
        int num = 1;

        while (count < n) {
            if (!seen.contains(k - num)) {
                seen.add(num);
                sum += num;
                count++;
            }
            num++;
        }
        return sum;
    }
}
```
### Algorithm
- Initialize a `HashSet<Integer>` named `seen`.
- Initialize `sum = 0L`, `count = 0`, and `num = 1`.
- Start a `while` loop that continues as long as `count < n`.
- Inside the loop, check if `seen` contains the value `k - num`.
- If it does not, add `num` to `seen`, add `num` to `sum`, and increment `count`.
- Increment `num` in every iteration.
- After the loop terminates, return `sum`.

## Mathematical Approach
By analyzing the pattern of the greedy approach, we can derive a direct mathematical formula to calculate the sum without any iteration. The key observation is that for any pair of integers `(i, k-i)`, we can include at most one in our array. To minimize the sum, we always choose the smaller one, `i`. This leads to a clear division of which numbers are chosen first.
**Time:** O(1). The solution involves a fixed number of arithmetic operations, regardless of the input values of `n` and `k`. · **Space:** O(1). The solution uses only a few variables to store intermediate calculations, not dependent on the input size.
**Pros:** Extremely efficient, with constant time complexity.; No extra space is required.; Provides a direct solution without simulation.
**Cons:** Requires mathematical insight to derive the formula, which might be less intuitive than the simulation.
### Explanation
The greedy strategy always picks the smallest available number. This means we will pick `1`, then `2`, and so on, as long as the k-avoiding property is maintained.

For any integer `i < k/2`, the pair is `(i, k-i)`. The greedy choice is to pick `i`. This means we will pick all integers from `1` up to `m = k/2` (integer division), provided we need that many numbers.

This observation splits the problem into two cases:

**Case 1: `n <= k / 2`**
If we need `n` numbers and `n` is less than or equal to `k/2`, we can simply pick the first `n` positive integers: `{1, 2, ..., n}`. The maximum sum of any two distinct elements in this set is `n + (n-1) = 2n-1`. Since `n <= k/2`, `2n <= k`, which means `2n-1 < k`. Thus, this set is k-avoiding. The minimum sum is the sum of the first `n` integers, which is `n * (n+1) / 2`.

**Case 2: `n > k / 2`**
Let `m = k / 2`. We first pick the smallest `m` integers that don't conflict with each other: `{1, 2, ..., m}`. The sum is `m * (m+1) / 2`.

By picking `{1, ..., m}`, we are forbidden from picking `{k-1, ..., k-m}`. The smallest number not yet picked or forbidden is `k`.

We have already picked `m` numbers and need `n - m` more. We pick the next `n - m` available numbers, which are `{k, k+1, ..., k + (n-m) - 1}`.

The sum of these additional numbers can be calculated using the arithmetic series formula.

The total sum is the sum of the first part (`1` to `m`) and the second part (`k` onwards).
```java
class Solution {
    public long minimumSum(int n, int k) {
        long m = k / 2;
        if (n <= m) {
            return (long)n * (n + 1) / 2;
        } else {
            long sum_first_part = m * (m + 1) / 2;
            long remaining_count = n - m;
            // The next numbers start from k. This is an arithmetic series:
            // k, k+1, ..., k + remaining_count - 1
            // Sum = count * (first + last) / 2
            // Sum = remaining_count * (k + k + remaining_count - 1) / 2
            long sum_second_part = remaining_count * (2L * k + remaining_count - 1) / 2;
            return sum_first_part + sum_second_part;
        }
    }
}
```
### Algorithm
- Calculate `m = k / 2`.
- Check if `n <= m`.
- If true, return the sum of the first `n` integers: `(long)n * (n + 1) / 2`.
- If false, it means `n > m`. Calculate the sum in two parts:
  - Part 1: Sum of the first `m` integers: `sum1 = (long)m * (m + 1) / 2`.
  - Part 2: We need `rem_count = n - m` more numbers. These numbers will be `k, k+1, ...`. Calculate the sum of this arithmetic series: `sum2 = rem_count * (2L * k + rem_count - 1) / 2`.
- Return `sum1 + sum2`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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

```