250+ TOP MCQs on Balanced Partition and Answers

Data Structure Multiple Choice Questions 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

Answer: d
Clarification: 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
Answer: c
Clarification: 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)
Answer: d
Clarification: 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}

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

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

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

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

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

& Algorithms.

and Answers.

Leave a Reply

Your email address will not be published. Required fields are marked *