What is meant by “nice permutations” in this question?

In this question, a nice permutation is a permutation of integers from 1 to N such that if in each round this permutation is followed by the people in the party to go to the food counter, then none of the persons get two consecutive chances to go to the food counter.

Why are all the possible permutations of integers from 1 to N nice if there are more than one person who can eat the highest number of plates?

If there are more than one people who can eat the highest number of plates of food, then upto the last round they will go one by one to the food counter and none of them will get two consecutive chances to go to the food counter, so all possible permutations will be nice permutations.

Nice Permutations - Naukri Code 360

Introduction

This section will discuss the problem “Nice Permutations”. First, let’s see the problem statement.

Problem statement-

Peter decided to host a party in which ‘N’ people gathered to eat. It is given that i^th person will eat a_i plates of food at the party. The plates of food were served in such a way that only one person could go to the food counter at a time and take one plate. So, Peter decides the order which will be followed by the gathered ‘N’ people in going to the food counter and taking the plate of food to eat. Let that order be a permutation ‘P’ of numbers from 1 to N.

( A permutation P is an array of integers of size N, in which each integer from 1 to N appears exactly once)

The order of people taking the plates of food will go as follows:

If person ‘P[0]’ has some plates left to eat, he will go to the food counter and take one plate, otherwise he will be skipped
If person ‘P[1]’ has some plates left to eat, he will go to the food counter and take one plate, otherwise he will be skipped
. . . . . . .
If person ‘P[N-2]’ has some plates left to eat, he will go to the food counter and take one plate, otherwise he will be skipped
If person ‘P[N-1]’ has some plates left to eat, he will go to the food counter and take one plate, otherwise, he will be skipped
If there are still people with number of plates left to eat, the process repeats from the start, otherwise, the process ends

According to Peter, a permutation ‘P’ is nice if none of the persons get two or more consecutive chances to go to the food counter and take the plates of food.

You will be given ‘N’, the number of people gathered in Peter’s party and an array ‘arr’ containing N integers, where arr[i] denotes the number of plates that the i^th person will eat in the party and your task is to count the number of nice permutations. The answer may be large, so print it modulo 998244353.

Solution Approach

This section will discuss the approach to solve the problem described in the previous section. We have to find the total number of nice permutations. Here nice permutations means the arrangement of ‘N’ people such that none of them get two consecutive chances to go to the food counter. The exact way in which they are getting the chance to go to the food counter is explained in the previous section.

Suppose the maximum number of plates a person can eat is ‘x’.

Case 1: If there are more than one person who can eat ‘x’ plates of food.

In this case, any permutation of integers from 1 to N will be a nice permutation because in the last round (the x^thround), each of these persons will go one by one and take the plate and none of them will get two consecutive chances to go to the food counter.

Case 2: If there is only one person who can eat ‘x’ plates of food.

Let ‘y’ be the index of the person who can eat the maximum number of plates. Then during the x-th round, there will be only one person left to go to the food counter. So, for a permutation to be a nice permutation, there should be a person in (x-1)-th round to go to the food counter after the y-th person. Let the number of persons who can eat (x-1) plates is ‘k’. If any of these ‘k’ persons will eat after the y-th person in the (x-1)-th round, then the permutation will be nice. We can count the bad permutations where none of the ‘k’ persons will eat after the y-th person in x-th round.

Total number of persons = N

Number of persons who can eat ‘x’ plates of food = 1

Number of persons who can eat ‘x-1’ plates of food = k

Number of persons who won’t eat ‘x’ or ‘x-1’ plates of food = N - k -1

Number of ways of getting bad permutations = (N! / (k+1)!) * (k!) = N! / (k+1)

So, number of good permutations = (Total permutations) - (Number of bad permutations)

= N! - N!/(k+1)

Algorithm -

Step 1. First, the main function. Inside the main function, create two variables ‘n’ and ‘arr’ to store the number of people at Peter’s party and the number of plates of food that each of these people will eat.

Step 2. Next, create the function “nicePermutations()” to find the number of nice permutations. It takes the following input parameters:

n: Number of people in the party
arr: Array denoting the number of plates of food that each of these people will eat

Step 3. Inside the function “nicePermutations()”, first initialise a variable ‘maxElement’ equal to the first element of ‘arr’ and then traverse the remaining elements of ‘arr’ and keep updating ‘maxElement’ to store the maximum element of ‘arr’ in it. Then create variables ‘countMaxElement’ and ‘k’ to store the count of ‘maxElement’ and ‘maxElement - 1’ respectively. Traverse the array ‘arr’ to find the value of these two variables.

Step 4. Now initialize the variables ‘ans’ and ‘bad’ to store the total number of permutations and number of bad permutations respectively. Run a ‘for loop’ and calculate the value of ‘ans’ and ‘bad’.

Step 5. Finally, check if the count of occurrence of ‘maxElement’ is greater than 1, then return the total number of permutations, else subtract the number of bad permutations from the total number of permutations and then return it.

C++ code:

// C++ program to find the number of nice permutations as described in the given problem
#include <bits/stdc++.h>
using namespace std;


#define mod 998244353


// Function to return the number of nice permutations as described in the given problem
int nicePermutations(int arr[], int n)
{

	// Variable to store the maximum element of arr
	int maxElement = arr[0];
	for(int i=1; i<n; i++)
	{
		if(arr[i] > maxElement) {
			maxElement = arr[i];
		}
	}

	// Variable to store the count of occurrence of maxElement in arr
	int countMaxElement = 0;
    	
	// Variable to store the count of occurence of (maxElement - 1) in arr
	int k = 0;
    	
	// Traversing arr to find the count of occurrences of maxElement and maxElement - 1
	for(int i=0; i<n; i++)
	{
		if(arr[i] == maxElement) {
			countMaxElement++;
		}
		if(arr[i] == maxElement - 1) {
			k++;
		}
	}
    
    // Variable to store the total number of permutations i.e n!
    int ans = 1;
    
    // Variable to store the number of bad permutations i.e (n!)/k+1
    int bad = 1;
    
    for(long long i = 1; i <= n; i++)
    {
    	ans = (ans * i) % mod;
    	if (i != k + 1) {
    		bad = (bad * i) % mod;
    	}
    }

	// If count of occurrence of maxElement is greater than one, then each permutation will be a nice permutation
	if(countMaxElement > 1) return ans;

	// Else, subtract the number of bad permutations from total number of permutations
	else {
		ans = (ans - bad + mod) % mod;
	}
	
	return ans;  
}
int main() 
{

    // Number of people in the party
    int n = 2;
    
    // Array storing the count of plates of food that each people will eat
    int arr[2] = {1, 2};
    
    // Call the function to find the total number of nice permutations
    int ans = nicePermutations(arr, n);
    
    cout<<"Total number of nice permutations are: "<<ans<<endl; 
 
 }

Output:
Total number of nice permutations are: 1

Algorithm Complexity:

Time Complexity: O(N)

In the function “nicePermutations()” to find the number of nice permutations as described in the given problem, three “for loops” are created to run from i=0 to i=n which will result in the time complexity of O(3 * N).

So, the overall time complexity will be approx O(N), where ‘N’ is the number of people gathered in Peter’s party.

Space Complexity: O(N)

In the function “nicePermutations()” to find the number of nice permutations as described in the given problem, constant space is used. So, the space complexity is O(1).

FAQs

What is meant by “nice permutations” in this question?
In this question, a nice permutation is a permutation of integers from 1 to N such that if in each round this permutation is followed by the people in the party to go to the food counter, then none of the persons get two consecutive chances to go to the food counter.
Why are all the possible permutations of integers from 1 to N nice if there are more than one person who can eat the highest number of plates?
If there are more than one people who can eat the highest number of plates of food, then upto the last round they will go one by one to the food counter and none of them will get two consecutive chances to go to the food counter, so all possible permutations will be nice permutations.

Key takeaways-

This article discussed the problem “Nice Permutations'', the solution approach to the problem, its C++ implementation, and its time and space complexity. If you want to solve more problems for practice, you can visit Coding Ninjas Studio.

If you think that this blog helped you, then share it with your friends!. Refer to the DSA C++ course for more information.

Until then, All the best for your future endeavours, and Keep Coding.