2829. Determine the Minimum Sum of a k-avoiding Array LeetCode Solution
In this guide, you will get 2829. Determine the Minimum Sum of a k-avoiding Array LeetCode Solution with the best time and space complexity. The solution to Determine the Minimum Sum of a k-avoiding Array problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Determine the Minimum Sum of a k-avoiding Array
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
Complexity Analysis
Time Complexity: O(1)
Space Complexity: O(1)
2829. Determine the Minimum Sum of a k-avoiding Array LeetCode Solution in C++
class Solution {
public:
int minimumSum(int n, int k) {
// These are the unique pairs that sum up to k:
// (1, k - 1), (2, k - 2), ..., (ceil(k / 2), floor(k / 2)).
// Our optimal strategy is to select 1, 2, ..., floor(k / 2), and then
// choose k, k + 1, ... if necessary, as selecting any number in the range
// [ceil(k / 2), k - 1] will result in a pair summing up to k.
const int mid = k / 2; // floor(k / 2)
if (n <= mid)
return trapezoid(1, n);
return trapezoid(1, mid) + trapezoid(k, k + (n - mid - 1));
}
private:
// Returns sum(a..b).
int trapezoid(int a, int b) {
return (a + b) * (b - a + 1) / 2;
}
}; /* code provided by PROGIEZ */
2829. Determine the Minimum Sum of a k-avoiding Array LeetCode Solution in Java
class Solution {
public int minimumSum(int n, int k) {
// These are the unique pairs that sum up to k:
// (1, k - 1), (2, k - 2), ..., (ceil(k / 2), floor(k / 2)).
// Our optimal strategy is to select 1, 2, ..., floor(k / 2), and then
// choose k, k + 1, ... if necessary, as selecting any number in the range
// [ceil(k / 2), k - 1] will result in a pair summing up to k.
final int mid = k / 2; // floor(k / 2)
if (n <= mid)
return trapezoid(1, n);
return trapezoid(1, mid) + trapezoid(k, k + (n - mid - 1));
}
// Returns sum(a..b).
private int trapezoid(int a, int b) {
return (a + b) * (b - a + 1) / 2;
}
} // code provided by PROGIEZ
2829. Determine the Minimum Sum of a k-avoiding Array LeetCode Solution in Python
class Solution:
def minimumSum(self, n: int, k: int) -> int:
# These are the unique pairs that sum up to k:
# (1, k - 1), (2, k - 2), ..., (ceil(k // 2), floor(k // 2)).
# Our optimal strategy is to select 1, 2, ..., floor(k // 2), and then
# choose k, k + 1, ... if necessary, as selecting any number in the range
# [ceil(k // 2), k - 1] will result in a pair summing up to k.
def trapezoid(a: int, b: int) -> int:
"""Returns sum(a..b)."""
return (a + b) * (b - a + 1) // 2
mid = k // 2 # floor(k // 2)
if n <= mid:
return trapezoid(1, n)
return trapezoid(1, mid) + trapezoid(k, k + (n - mid - 1)) # code by PROGIEZ
