Input: n =5, k =4Output: 18Explanation: 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.
Input: n =2, k =6Output: 3Explanation: 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.
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.
classSolution {
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;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
funcminimumSum(nint, kint) int {
used:=map[int]bool{}
ans, x, cnt:=0, 1, 0forcnt < n {
if !used[k-x] {
ans+=xused[x] = truecnt++ }
x++ }
returnans}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
classSolution {
publicintminimumSum(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;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
classSolution {
funminimumSum(n: Int, k: Int): Int {
val used = mutableSetOf<Int>()
var ans = 0var x = 1var cnt = 0while (cnt < n) {
if ((k - x) !in used) {
ans += x
used.add(x)
cnt++ }
x++ }
return ans
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
classSolution:
defminimumSum(self, n: int, k: int) -> int:
used = set()
ans =0 x =1 cnt =0while cnt < n:
if k - x notin used:
ans += x
used.add(x)
cnt +=1 x +=1return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
impl Solution {
pubfnminimum_sum(n: i32, k: i32) -> i32 {
use std::collections::HashSet;
letmut used = HashSet::new();
letmut ans =0;
letmut x =1;
letmut cnt =0;
while cnt < n {
if!used.contains(&(k - x)) {
ans += x;
used.insert(x);
cnt +=1;
}
x +=1;
}
ans
}
}