This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Balanced Partition”.
1. Given an array, check if the array can be divided into two subsets such that the sum of elements of the two subsets is equal. This is the balanced partition problem. Which of the following methods can be used to solve the balanced partition problem?
a) Dynamic programming
b) Recursion
c) Brute force
d) Dynamic programming, Recursion, Brute force
View Answer
Explanation: All of the mentioned methods can be used to solve the balanced partition problem.
2. In which of the following cases, it is not possible to have two subsets with equal sum?
a) When the number of elements is odd
b) When the number of elements is even
c) When the sum of elements is odd
d) When the sum of elements is even
View Answer
Explanation: When the sum of all the elements is odd, it is not possible to have two subsets with equal sum.
3. What is the time complexity of the brute force algorithm used to solve the balanced partition problem?
a) O(1)
b) O(n)
c) O(n2)
d) O(2n)
View Answer
Explanation: In the brute force implementation, all the possible subsets will be formed. This takes exponential time.
4. Consider a variation of the balanced partition problem in which we find two subsets such that |S1 – S2| is minimum. Consider the array {1, 2, 3, 4, 5}. Which of the following pairs of subsets is an optimal solution for the above problem?
a) {5, 4} & {3, 2, 1}
b) {5} & {4, 3, 2, 1}
c) {4, 2} & {5, 3, 1}
d) {5, 3} & {4, 2, 1}
View Answer
Explanation: For S1 = {5, 3} and S2 = {4, 2, 1}, sum(S1) – sum(S2) = 1, which is the optimal solution.
5. Consider the following code:
#include<stdio.h> int balanced_partition(int *arr, int len) { int sm = 0, i, j; for(i = 0;i < len; i++) sm += arr[i]; if(sm % 2 != 0) return 0; int ans[sm/2 + 1][len + 1]; for(i = 0; i <= len; i++) ans[0][i] = 1; for(i = 1; i <= sm/2; i++) ans[i][0] = 0; for(i = 1; i <= sm/2; i++) { for(j = 1;j <= len; j++) { ans[i][j] = ans[i][j-1]; if(i >= arr[j - 1]) ans[i][j] = _______________; } } return ans[sm/2][len]; } int main() { int arr[] = {3, 4, 5, 6, 7, 1}, len = 6; int ans = balanced_partition(arr,len); if(ans == 0) printf("false"); else printf("true"); return 0; }
Which of the following lines should be inserted to complete the above code?
a) ans[i – arr[j – 1]][j – 1]
b) ans[i][j]
c) ans[i][j] || ans[i – arr[j – 1]][j – 1]
d) ans[i][j] && ans[i – arr[j – 1]][j – 1]
View Answer
Explanation: The line “ans[i][j] || ans[i – arr[j – 1]][j – 1]” completes the above code.
6. What is the time complexity of the following dynamic programming implementation of the balanced partition problem where “n” is the number of elements and “sum” is their sum?
#include<stdio.h> int balanced_partition(int *arr, int len) { int sm = 0, i, j; for(i = 0;i < len; i++) sm += arr[i]; if(sm % 2 != 0) return 0; int ans[sm/2 + 1][len + 1]; for(i = 0; i <= len; i++) ans[0][i] = 1; for(i = 1; i <= sm/2; i++) ans[i][0] = 0; for(i = 1; i <= sm/2; i++) { for(j = 1;j <= len; j++) { ans[i][j] = ans[i][j-1]; if(i >= arr[j - 1]) ans[i][j] = ans[i][j] || ans[i - arr[j - 1]][j - 1]; } } return ans[sm/2][len]; } int main() { int arr[] = {3, 4, 5, 6, 7, 1}, len = 6; int ans = balanced_partition(arr,len); if(ans == 0) printf("false"); else printf("true"); return 0; }
a) O(sum)
b) O(n)
c) O(sum * n)
d) O(sum + n)
View Answer
Explanation: The time complexity of the above dynamic programming implementation of the balanced partition problem is O(sum * n).
7. What is the space complexity of the following dynamic programming implementation of the balanced partition problem?
#include<stdio.h> int balanced_partition(int *arr, int len) { int sm = 0, i, j; for(i = 0;i < len; i++) sm += arr[i]; if(sm % 2 != 0) return 0; int ans[sm/2 + 1][len + 1]; for(i = 0; i <= len; i++) ans[0][i] = 1; for(i = 1; i <= sm/2; i++) ans[i][0] = 0; for(i = 1; i <= sm/2; i++) { for(j = 1;j <= len; j++) { ans[i][j] = ans[i][j-1]; if(i >= arr[j - 1]) ans[i][j] = ans[i][j] || ans[i - arr[j - 1]][j - 1]; } } return ans[sm/2][len]; } int main() { int arr[] = {3, 4, 5, 6, 7, 1}, len = 6; int ans = balanced_partition(arr,len); if(ans == 0) printf("false"); else printf("true"); return 0; }
a) O(sum)
b) O(n)
c) O(sum * n)
d) O(sum + n)
View Answer
Explanation: The space complexity of the above dynamic programming implementation of the balanced partition problem is O(sum * n).
8. What is the output of the following code?
#include<stdio.h> int balanced_partition(int *arr, int len) { int sm = 0, i, j; for(i = 0;i < len; i++) sm += arr[i]; if(sm % 2 != 0) return 0; int ans[sm/2 + 1][len + 1]; for(i = 0; i <= len; i++) ans[0][i] = 1; for(i = 1; i <= sm/2; i++) ans[i][0] = 0; for(i = 1; i <= sm/2; i++) { for(j = 1;j <= len; j++) { ans[i][j] = ans[i][j-1]; if(i >= arr[j - 1]) ans[i][j] = ans[i][j] || ans[i - arr[j - 1]][j - 1]; } } return ans[sm/2][len]; } int main() { int arr[] = {3, 4, 5, 6, 7, 1}, len = 6; int ans = balanced_partition(arr,len); if(ans == 0) printf("false"); else printf("true"); return 0; }
a) True
b) False
View Answer
Explanation: The partitions are S1 = {6, 7} and S2 = {1, 3, 4, 5} and the sum of each partition is 13. So, the array can be divided into balanced partitions.
9. What is the value stored in ans[3][3] when the following code is executed?
#include<stdio.h> int balanced_partition(int *arr, int len) { int sm = 0, i, j; for(i = 0;i < len; i++) sm += arr[i]; if(sm % 2 != 0) return 0; int ans[sm/2 + 1][len + 1]; for(i = 0; i <= len; i++) ans[0][i] = 1; for(i = 1; i <= sm/2; i++) ans[i][0] = 0; for(i = 1; i <= sm/2; i++) { for(j = 1;j <= len; j++) { ans[i][j] = ans[i][j-1]; if(i >= arr[j - 1]) ans[i][j] = ans[i][j] || ans[i - arr[j - 1]][j - 1]; } } return ans[sm/2][len]; } int main() { int arr[] = {3, 4, 5, 6, 7, 1}, len = 6; int ans = balanced_partition(arr,len); if(ans == 0) printf("false"); else printf("true"); return 0; }
a) 0
b) 1
c) -1
d) -2
View Answer
Explanation: The value stored in ans[3][3] indicates if a sum of 3 can be obtained using a subset of the first 3 elements. Since the sum can be obtained the value stored is 1.
10. What is the sum of each of the balanced partitions for the array {5, 6, 7, 10, 3, 1}?
a) 16
b) 32
c) 0
d) 64
View Answer
Explanation: The sum of all the elements of the array is 32. So, the sum of all the elements of each partition should be 16.
11. What is the output of the following code?
#include<stdio.h> int balanced_partition(int *arr, int len) { int sm = 0, i, j; for(i = 0;i < len; i++) sm += arr[i]; if(sm % 2 != 0) return 0; int ans[sm/2 + 1][len + 1]; for(i = 0; i <= len; i++) ans[0][i] = 1; for(i = 1; i <= sm/2; i++) ans[i][0] = 0; for(i = 1; i <= sm/2; i++) { for(j = 1;j <= len; j++) { ans[i][j] = ans[i][j-1]; if(i >= arr[j - 1]) ans[i][j] = ans[i][j] || ans[i - arr[j - 1]][j - 1]; } } return ans[sm/2][len]; } int main() { int arr[] = {5, 6, 7, 10, 3, 1}, len = 6; int ans = balanced_partition(arr,len); if(ans == 0) printf("false"); else printf("true"); return 0; }
a) True
b) False
View Answer
Explanation: The array can be divided into two partitions S1 = {10, 6} and S2 = {5, 7, 3, 1} and the sum of all the elements of each partition is 16. So, the answer is true.
12. What is the output of the following code?
#include<stdio.h> int balanced_partition(int *arr, int len) { int sm = 0, i, j; for(i = 0;i < len; i++) sm += arr[i]; if(sm % 2 != 0) return 0; int ans[sm/2 + 1][len + 1]; for(i = 0; i <= len; i++) ans[0][i] = 1; for(i = 1; i <= sm/2; i++) ans[i][0] = 0; for(i = 1; i <= sm/2; i++) { for(j = 1;j <= len; j++) { ans[i][j] = ans[i][j-1]; if(i >= arr[j - 1]) ans[i][j] = ans[i][j] || ans[i - arr[j - 1]][j - 1]; } } return ans[sm/2][len]; } int main() { int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9}, len = 9; int ans = balanced_partition(arr,len); if(ans == 0) printf("false"); else printf("true"); return 0; }
a) True
b) False
View Answer
Explanation: Since the sum of all the elements of the array is 45, the array cannot be divided into two partitions of equal sum and the answer is false.
Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.
To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.
If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]
- Practice Data Structure MCQ
- Check Design and Analysis of Algorithms Books
- Check Programming Books
- Apply for Computer Science Internship
- Practice Programming MCQs
