Data Structure Questions and Answers – Balanced Partition

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

Answer: d
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

Answer: c
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

Answer: d
Explanation: In the brute force implementation, all the possible subsets will be formed. This takes exponential time.
advertisement
advertisement

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

Answer: d
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

Answer: c
Explanation: The line “ans[i][j] || ans[i – arr[j – 1]][j – 1]” completes the above code.
advertisement

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

Answer: c
Explanation: The time complexity of the above dynamic programming implementation of the balanced partition problem is O(sum * n).
advertisement

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

Answer: c
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

Answer: a
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

Answer: b
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

Answer: a
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

Answer: a
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

Answer: b
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.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.