Number of ways whose sum is greater than or equal to K

By Ann Roberts On Jan 27, 2023

Given an array, arr[], and an integer K, the task is to find the total number of ways in which we can divide the array into two groups such that the sum of each group is greater than equal to K and each element belongs to one of these groups.

Examples:

Input: arr[ ] = [6, 6], K = 2
Output: 2
Explanation: The partitions are ([6], [6]) and ([6], [6]) since both the 6 at index 0 and 1 are treated differently.

Input: arr[ ] = [1, 2, 3, 4], K = 4
Output: 6
Explanation: The 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]).

Approach: The problem can be solved based on the following observation:

Try to solve this problem recursively where we will find out the number of subsets whose sum is less than K and store this in an array to avoid calculating the same thing again and again. Finally, we will subtract this from the total subsets to find the desired answer. This in turn will reduce our time complexity. Yes, you guess it right we are about to apply the dynamic programming concept.

Follow the steps mentioned below to implement the idea:

If the sum of elements in the array is less than twice K then a way cannot be made.
we will make dp with all pairs whose sum is less than k
Generate pairs for all sums from 0 to K – 1
Collect all the power sets.
Finally, we will perform an operation where (way whose sum is greater than K = Total partitions – partitions whose (sum < K)).

Below is the Implementation of the above approach:

C++

#include <bits/stdc++.h>

using namespace std;

int cntWays(vector<int>& arr, int K)

{

int ans = 1;

vector<int> dp(K, 0);

long total = 0;

dp[0] = 1;

int lessThanK = K - 1;

for (auto& n : arr) {

for (int i = lessThanK - n; i >= 0; i--) {

dp[i + n] = (dp[i + n] + dp[i]);

}

ans = ans * 2;

total += n;

}

if (total < 2 * K)

return 0;

long sumlessthanK = 0;

for (int i = 0; i <= lessThanK; ++i) {

sumlessthanK = (sumlessthanK + dp[i]);

}

ans = (ans - (2 * sumlessthanK));

return ans;

}

int main()

{

vector<int> arr{ 1, 2, 3, 4 };

int K = 4;

cout << cntWays(arr, K);

return 0;

}

Time Complexity: O(n*K)
Auxilairy Space: O(sum)

Examples:

Input: arr[ ] = [6, 6], K = 2
Output: 2
Explanation: The partitions are ([6], [6]) and ([6], [6]) since both the 6 at index 0 and 1 are treated differently.

Input: arr[ ] = [1, 2, 3, 4], K = 4
Output: 6
Explanation: The 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]).

Approach: The problem can be solved based on the following observation:

Try to solve this problem recursively where we will find out the number of subsets whose sum is less than K and store this in an array to avoid calculating the same thing again and again. Finally, we will subtract this from the total subsets to find the desired answer. This in turn will reduce our time complexity. Yes, you guess it right we are about to apply the dynamic programming concept.

Follow the steps mentioned below to implement the idea:

If the sum of elements in the array is less than twice K then a way cannot be made.
we will make dp with all pairs whose sum is less than k
Generate pairs for all sums from 0 to K – 1
Collect all the power sets.
Finally, we will perform an operation where (way whose sum is greater than K = Total partitions – partitions whose (sum < K)).

Below is the Implementation of the above approach:

C++

#include <bits/stdc++.h>

using namespace std;

int cntWays(vector<int>& arr, int K)

{

int ans = 1;

vector<int> dp(K, 0);

long total = 0;

dp[0] = 1;

int lessThanK = K - 1;

for (auto& n : arr) {

for (int i = lessThanK - n; i >= 0; i--) {

dp[i + n] = (dp[i + n] + dp[i]);

}

ans = ans * 2;

total += n;

}

if (total < 2 * K)

return 0;

long sumlessthanK = 0;

for (int i = 0; i <= lessThanK; ++i) {

sumlessthanK = (sumlessthanK + dp[i]);

}

ans = (ans - (2 * sumlessthanK));

return ans;

}

int main()

{

vector<int> arr{ 1, 2, 3, 4 };

int K = 4;

cout << cntWays(arr, K);

return 0;

}

Time Complexity: O(n*K)
Auxilairy Space: O(sum)

Read original article here

Denial of responsibility! Techno Blender is an automatic aggregator of the all world’s media. In each content, the hyperlink to the primary source is specified. All trademarks belong to their rightful owners, all materials to their authors. If you are the owner of the content and do not want us to publish your materials, please contact us by email – [email protected]. The content will be deleted within 24 hours.