250+ TOP MCQs on Generating Partitions and Answers [2024]

Data Structures & Algorithms Multiple Choice Questions on “Generating Partitions”.

1. What is meant by integer partition?
a) representing an integer as sum of positive and negative real numbers
b) representing an integer as sum of positive and negative integers
c) representing an integer as sum of positive integers
d) representing an integer as sum of positive real numbers

Answer: c
Clarification: Integer partition is the way of representing an integer as sum of positive integers. Partitions differing only in their order are considered to be same.

2. How many partitions will be formed for the integer 3?
a) 2
b) 3
c) 4
d) 8

Answer: b
Clarification: We need to find the combinations of positive integers which give 3 as their sum. These will be {3}, {2,1}, {1,1,1}. Thus the correct answer is 3.

3. What is meant by number theory?
a) study of integers
b) study of complex numbers
c) numerology
d) theory of origination of mathematics

Answer: a
Clarification: Number theory is a branch of mathematics that deals with the study of integers. Partitioning of a number comes under the study of number theory.

4. Which of the following is true according to Ramanujan’s congruence?
a) No. of partitions are divisible by 5 for a number 3 more than a multiple of 5
b) No. of partitions are divisible by 5 for a number 4 more than a multiple of 5
c) No. of partitions are divisible by 5 for a number 2 more than a multiple of 5
d) No. of partitions are divisible by 5 for a number 1 more than a multiple of 5

Answer: b
Clarification: Ramanujan’s congruence are some relations found for the no. of partitions of an integer. According to it, the number of partitions of an integer is divisible by 5 if that integer is 4 more than a multiple of 5.

5. The no. of partitions of which of the following integer will be divisible by 5?
a) 3
b) 5
c) 9
d) 6

Answer: c
Clarification: According to Ramanujan’s congruence number of partitions of an integer is divisible by 5 if that integer is 4 more than a multiple of 5. So out of the given options 9 is the only integer which satisfies this condition.

6. What is the output of the following code?

#include 
using namespace std;  
void printArray(int p[], int n) 
{ 
	for (int i = 0; i <= n-1; i++) 
	cout << p[i] << " "; 
	cout << endl; 
} 
void func1(int n) 
{ 
	int p[n];  
	int k = 0;  
	p[k] = n; 	
	while (true) 
	{ 		
		printArray(p, k+1); 		
		int rem_val = 0; 
		while (k >= 0 && p[k] == 1) 
		{ 
			rem_val += p[k]; 
			k--; 
		} 
		if (k < 0) return; 	
		p[k]--; 
		rem_val++; 		
		while (rem_val > p[k]) 
		{ 
			p[k+1] = p[k]; 
			rem_val = rem_val - p[k]; 
			k++; 
		} 
		p[k+1] = rem_val; 
		k++; 
	} 
} 
int main() 
{ 
int n=3;
	func1(n);
	return 0; 
}

  3 
  1 2
  1 1 1

  1 1 1
  2 1
  3

  1 1 1
  1 2
  3

   3
   2 1
   1 1 1

Answer: d
Clarification: The given code prints the partition of a number in decreasing order. This code uses the approach of dynamic programming.

7. While generating partitions of integer 3 we consider 2 1 and 1 2 to be different partitions.
a) true
b) false

Answer: b
Clarification: Partitions differing in order are considered to be same. Thus 2 1 and 1 2 are considered to be same when we generate partitions of integer 3.

8. What is the approach implemented in the following code?

#include 
using namespace std;  
void printArray(int p[], int n) 
{ 
	for (int i = 0; i <= n-1; i++) 
	cout << p[i] << " "; 
	cout << endl; 
} 
void func1(int n) 
{ 
	int p[n];  
	int k = 0;  
	p[k] = n; 	
	while (true) 
	{ 		
		printArray(p, k+1); 		
		int rem_val = 0; 
		while (k >= 0 && p[k] == 1) 
		{ 
			rem_val += p[k]; 
			k--; 
		} 
		if (k < 0) return; 	
		p[k]--; 
		rem_val++; 		
		while (rem_val > p[k]) 
		{ 
			p[k+1] = p[k]; 
			rem_val = rem_val - p[k]; 
			k++; 
		} 
		p[k+1] = rem_val; 
		k++; 
	} 
} 
 
int main() 
{ 
      int n;
      cin>>n;
      func1(n);
      return 0; 
}

a) greedy approach
b) dynamic programming
c) recursion(divide and conquer)
d) backtracking
Answer: b
Clarification: The given code prints the partition of a number in decreasing order. This code uses the approach of dynamic programming. We can also use recursion for fulfilling the same purpose.

9. What will be the output of the following code?

#include
using namespace std;
int list[200];
void func(int n, int m = 0)
{
    int i;
    if(n == 0)
    {
         for(i = 0; i < m; ++i)
         printf("%d ", list[i]);
         printf("n");
         return;
    }
    for(i = n; i > 0; --i)
    {
         if(m == 0 || i <= list[m - 1])
         {
             list[m] = i;
             func(n - i, m + 1);
         }
    }
 
}
int main()
{
	int n=3;
	func(n,0);
	return 0;
}

  3 
  2 1
  1 1 1

  1 1 1
  2 1
  3

  1 1 1
  1 2
  3

   3
   1 2
   1 1 1

Answer: a
Clarification: The given code prints the partition of a number in decreasing order. This code uses the approach of recursion. The same purpose can be fulfilled by using dynamic programming.

10. Which of the following correctly represents the code to print partitions of a number?
a)

#include
using namespace std;
int print[200];
void partitn(int n,int k,int idx)
{
 
	if(n==0)
        {
		for(int i=0;i<idx;i++)
			cout<<print[i]<<" ";
		cout<<endl;
	        return ;
        }
	for(int i=k;i>0;i--)
        {
		if(i>n)continue; 
		print[idx]=i;					 
		partitn(n-i,i,idx+1);
	}
}
int main()
{
	int n;
	cin>>n;
	partitn(n,n,0);
	return 0;
}

#include
using namespace std;
int print[200];
void partitn(int n,int k,int idx)
{	
	if(n==0)
        {
		for(int i=0;i<idx;i++)
			cout<<print[i]<<" ";
		cout<<endl;
	        return ;
        }
	for(int i=k;i>0;i--)
        {
		if(i>n)continue; 
		print[idx]=i;					 
		partitn(n-i,i,idx+1);
	}
}
int main()
{
	int n;
	cin>>n;
	partitn(n,0,0);
	return 0;
}

#include
using namespace std;
int print[200];
void partitn(int n,int k,int idx)
{	
	if(n==0)
        {
		for(int i=0;i<idx;i++)
			cout<<print[i]<<" ";
		cout<<endl;
	        return ;
        }
	for(int i=k;i>0;i--)
        {
		print[idx]=i;					 
		partitn(n-i,i,idx+1);
	}
}
int main()
{
	int n;
	cin>>n;
	partitn(n,0,0);
	return 0;
}

#include
using namespace std;
int print[200];
void partitn(int n,int k,int idx)
{	
	if(n==0)
        {
		for(int i=0;i<idx;i++)
			cout<<print[i]<<" ";
		cout<<endl;
	        return ;
        }
	for(int i=k;i>0;i--)      
        { 
		print[idx]=i;					 
		partitn(n-i,i,idx+1);
	}
}
int main()
{
	int n;
	cin>>n;
	partitn(n,n,0);
	return 0;
}

Answer: a
Clarification: In the correct code we need to pass n as second argument in the function partitn() and need to check for the condition i>n. The code prints the partitions in decreasing order.

and Answers.

Leave a Reply Cancel reply