2518. Number of Great Partitions LeetCode Solution
In this guide, you will get 2518. Number of Great Partitions LeetCode Solution with the best time and space complexity. The solution to Number of Great Partitions 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.
You are given an array nums consisting of positive integers and an integer k.
Partition the array into two ordered groups such that each element is in exactly one group. A partition is called great if the sum of elements of each group is greater than or equal to k.
Return the number of distinct great partitions. Since the answer may be too large, return it modulo 109 + 7.
Two partitions are considered distinct if some element nums[i] is in different groups in the two partitions.
Example 1:
Input: nums = [1,2,3,4], k = 4
Output: 6
Explanation: The great partitions are: ([1,2,3], [4]), ([1,3], [2,4]), ([1,4], [2,3]), ([2,3], [1,4]), ([2,4], [1,3]) and ([4], [1,2,3]).
Example 2:
Input: nums = [3,3,3], k = 4
Output: 0
Explanation: There are no great partitions for this array.
Example 3:
Input: nums = [6,6], k = 2
Output: 2
Explanation: We can either put nums[0] in the first partition or in the second partition.
The great partitions will be ([6], [6]) and ([6], [6]).
2518. Number of Great Partitions LeetCode Solution in C++
class Solution {
public:
int countPartitions(vector<int>& nums, int k) {
const long sum = accumulate(nums.begin(), nums.end(), 0L);
long ans = modPow(2, nums.size());
vector<long> dp(k + 1);
dp[0] = 1;
for (const int num : nums)
for (int i = k; i >= num; --i) {
dp[i] += dp[i - num];
dp[i] %= kMod;
}
// Substract the cases that're not satisfied.
for (int i = 0; i < k; ++i)
if (sum - i < k) // Both group1 and group2 < k.
ans -= dp[i];
else
ans -= dp[i] * 2;
return (ans % kMod + kMod) % kMod;
}
private:
static constexpr int kMod = 1'000'000'007;
long modPow(long x, long n) {
if (n == 0)
return 1;
if (n % 2 == 1)
return x * modPow(x % kMod, (n - 1)) % kMod;
return modPow(x * x % kMod, (n / 2)) % kMod;
}
}; /* code provided by PROGIEZ */
2518. Number of Great Partitions LeetCode Solution in Java
class Solution {
public int countPartitions(int[] nums, int k) {
final int kMod = 1_000_000_007;
final long sum = Arrays.stream(nums).asLongStream().sum();
long ans = modPow(2, nums.length, kMod); // 2^n % kMod
long[] dp = new long[k + 1];
dp[0] = 1;
for (final int num : nums)
for (int i = k; i >= num; --i) {
dp[i] += dp[i - num];
dp[i] %= kMod;
}
// Substract the cases that're not satisfied.
for (int i = 0; i < k; ++i)
if (sum - i < k) // Both group1 and group2 < k.
ans -= dp[i];
else
ans -= dp[i] * 2;
return (int) ((ans % kMod + kMod) % kMod);
}
private int modPow(int x, int n, int kMod) {
int res = 1;
for (int i = 0; i < n; ++i)
res = res * x % kMod;
return res;
}
} // code provided by PROGIEZ
2518. Number of Great Partitions LeetCode Solution in Python
class Solution:
def countPartitions(self, nums: list[int], k: int) -> int:
kMod = 1_000_000_007
summ = sum(nums)
ans = pow(2, len(nums), kMod) # 2^n % kMod
dp = [1] + [0] * k
for num in nums:
for i in range(k, num - 1, -1):
dp[i] += dp[i - num]
dp[i] %= kMod
# Substract the cases that're not satisfied.
for i in range(k):
if summ - i < k: # Both group1 and group2 < k.
ans -= dp[i]
else:
ans -= dp[i] * 2
return ans % kMod # code by PROGIEZ
