Determine the Minimum Sum of a k-avoiding Array — Solution
Determine the Minimum Sum of a k-avoiding Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Determine the Minimum Sum of a k-avoiding Array is a medium coding problem on arrays, math and greedy, asked in Amazon, Google and Oracle interviews.
- Difficulty: Medium
- Topics: Arrays, Math, Greedy
- Asked at: Amazon, Google, Oracle
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
An array of distinct positive integers is k-avoiding if no two different elements 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: `[1,2,4,5,6]` — 3 is skipped because `1 + 3 = 4`.
Example 2
Input: n = 2, k = 6
Output: 3
Explanation: `[1,2]` sums to 3 and avoids 6.
Example 3
Input: n = 1, k = 1
Output: 1
Constraints
1 <= n, k <= 50
Hints for Determine the Minimum Sum of a k-avoiding Array
Hint 1
Take the smallest numbers you can, in order.
Hint 2
A number
vis blocked only ifk - vhas already been taken.Hint 3
Once past
k, nothing is ever blocked again.
How to solve Determine the Minimum Sum of a k-avoiding Array
Greedily take 1, 2, 3, …, skipping any v whose partner k - v is already in the array. Stop once n numbers have been taken.
Approach
- Keep a set of chosen numbers and walk
vupward from 1. - Take
vwhenk - vis not already chosen. - Stop after
nnumbers and return their sum.
Why it works
Taking the smallest available number is safe because the numbers it blocks are all larger than it, so no cheaper option is ever lost. The pattern this produces is 1 … ⌊(k-1)/2⌋ followed by k, k+1, … — every pair inside the first block sums to less than k, and every number from k upward has a partner that is zero or negative.
Complexity
- Time —
O(n + k) - Space —
O(n)
Pitfalls
- The two elements of a forbidden pair must be different, so
kbeing even does not rule outk/2on its own. - Numbers at or above
kare never blocked. - The array must hold exactly
ndistinct numbers.
Reference solution
Python
def minimumSum(n: int, k: int) -> int:
used = set()
total = 0
v = 1
while len(used) < n:
if k - v not in used:
used.add(v)
total += v
v += 1
return totalJava
public static int minimumSum(int n, int k) {
Set<Integer> used = new HashSet<>();
int sum = 0, v = 1;
while (used.size() < n) {
if (!used.contains(k - v)) {
used.add(v);
sum += v;
}
v++;
}
return sum;
}C++
int minimumSum(int n, int k) {
unordered_set<int> used;
int sum = 0, v = 1;
while ((int) used.size() < n) {
if (used.find(k - v) == used.end()) {
used.insert(v);
sum += v;
}
v++;
}
return sum;
}JavaScript
var minimumSum = function(n, k) {
var used = {};
var sum = 0, v = 1, taken = 0;
while (taken < n) {
if (!used["" + (k - v)]) {
used["" + v] = true;
sum += v;
taken++;
}
v++;
}
return sum;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Greedy Algorithms