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
Solution 1: Greedy + HashTable
Always choose the smallest possible number starting from 1.
Add all chosen numbers into a hashtable. For a new candidate i, check whether k – i is already in the hashtable.
Time complexity: O(n)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
// Author: Huahua class Solution { public: int minimumSum(int n, int k) { int sum = 0; unordered_set<int> s; for (int i = 1; s.size() != n; ++i) { if (s.count(k - i)) continue; sum += i; s.insert(i); } return sum; } }; |