2834. Find the Minimum Possible Sum of a Beautiful Array LeetCode Solution
In this guide, you will get 2834. Find the Minimum Possible Sum of a Beautiful Array LeetCode Solution with the best time and space complexity. The solution to Find the Minimum Possible Sum of a Beautiful 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 Find the Minimum Possible Sum of a Beautiful Array
You are given positive integers n and target.
An array nums is beautiful if it meets the following conditions:
nums.length == n.
nums consists of pairwise distinct positive integers.
There doesn’t exist two distinct indices, i and j, in the range [0, n – 1], such that nums[i] + nums[j] == target.
Return the minimum possible sum that a beautiful array could have modulo 109 + 7.
Example 1:
Input: n = 2, target = 3
Output: 4
Explanation: We can see that nums = [1,3] is beautiful.
– The array nums has length n = 2.
– The array nums consists of pairwise distinct positive integers.
– There doesn’t exist two distinct indices, i and j, with nums[i] + nums[j] == 3.
It can be proven that 4 is the minimum possible sum that a beautiful array could have.
Input: n = 3, target = 3
Output: 8
Explanation: We can see that nums = [1,3,4] is beautiful.
– The array nums has length n = 3.
– The array nums consists of pairwise distinct positive integers.
– There doesn’t exist two distinct indices, i and j, with nums[i] + nums[j] == 3.
It can be proven that 8 is the minimum possible sum that a beautiful array could have.
Example 3:
Input: n = 1, target = 1
Output: 1
Explanation: We can see, that nums = [1] is beautiful.
Constraints:
1 <= n <= 109
1 <= target <= 109
Complexity Analysis
Time Complexity: O(1)
Space Complexity: O(1)
2834. Find the Minimum Possible Sum of a Beautiful Array LeetCode Solution in C++
class Solution {
public:
// Same as 2829. Determine the Minimum Sum of a k-avoiding Array
int minimumPossibleSum(int n, int target) {
// These are the unique pairs that sum up to target (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 = target / 2;
if (n <= mid)
return trapezoid(1, n);
return (trapezoid(1, mid) + trapezoid(target, target + (n - mid - 1))) %
kMod;
}
private:
static constexpr int kMod = 1'000'000'007;
// Returns sum(a..b).
long trapezoid(long a, long b) {
return (a + b) * (b - a + 1) / 2;
}
}; /* code provided by PROGIEZ */
2834. Find the Minimum Possible Sum of a Beautiful Array LeetCode Solution in Java
class Solution {
// Same as 2829. Determine the Minimum Sum of a k-avoiding Array
public int minimumPossibleSum(int n, int target) {
// These are the unique pairs that sum up to target (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 = target / 2; // floor(k / 2)
if (n <= mid)
return (int) trapezoid(1, n);
return (int) ((trapezoid(1, mid) + trapezoid(target, target + (n - mid - 1))) % kMod);
}
private static final int kMod = 1_000_000_007;
// Returns sum(a..b).
private long trapezoid(long a, long b) {
return (a + b) * (b - a + 1) / 2;
}
} // code provided by PROGIEZ
2834. Find the Minimum Possible Sum of a Beautiful Array LeetCode Solution in Python
class Solution:
# Same as 2829. Determine the Minimum Sum of a k-avoiding Array
def minimumPossibleSum(self, n: int, target: int) -> int:
# These are the unique pairs that sum up to k (target):
# (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.
kMod = 1_000_000_007
def trapezoid(a: int, b: int) -> int:
"""Returns sum(a..b)."""
return (a + b) * (b - a + 1) // 2
mid = target // 2 # floor(k // 2)
if n <= mid:
return trapezoid(1, n)
return (trapezoid(1, mid) + trapezoid(target, target + (n - mid - 1))) % kMod # code by PROGIEZ
