1.
Introduction
2.
Solution Approach
3.
Algorithm -
4.
C++ code:
4.1.
Algorithm Complexity:
5.
FAQs
6.
Key takeaways-
Last Updated: Mar 27, 2024

# Nice Permutations

Riya
1 upvote

## 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 ith person will eat ai 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 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 ith 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.

Let’s take an example to understand the given problem:

Suppose N = 2 and arr = {1, 2}

It means there are two people who came to Peter’s party and the 1st  person will eat one plate of food and the 2nd person will eat two plates of food.

Permutations of numbers from 1 to 2 are: {1, 2} and {2, 1}

Let's check these two permutations one by one if they are nice or not.

Permutation 1: P1 = {1, 2}

• P1[0] = 1: 1st person will go to the food counter and take one plate. Remaining plate for 1st person = arr[0] - 1 = 1 - 1 = 0

So, arr = {0, 2}

• P1[1] = 2: 2nd person will go to the food counter and take one plate. Remaining plate for 2nd person = arr[1] - 1 = 2 -1 = 1

So, arr = {0, 1}

One round of the permutation finished but still one plate of food is left for the 2nd person as now arr = {0, 1}. So, the process will repeat from the start.

• P1[0] = 1: 1st person has 0 plates left to eat, so he will be skipped.
• P1[1] = 2: 2nd person will go to the food counter and take one plate. Remaining plate for 2nd person = arr[1] - 1 = 1 -1 = 0

So, arr = {0, 0}

Now, none of the persons has left any number of plates to eat (as arr has become {0, 0}), so the process will stop. Three plates of food are taken from the food counter and the people reached the food counter in the following order:

{1, 2, 2}

Here we can see that the 2nd person has got two consecutive chances to go to the food counter and take a plate. So, this permutation is not a nice permutation.

Permutation 2: P2 = {2, 1}

• P2[0] = 2: 2nd person will go to the food counter and take one plate. Remaining plate for 2nd person = arr[1] - 1 = 2 - 1 = 1

So, arr = {1, 1}

• P1[1] = 1: 1st person will go to the food counter and take one plate. Remaining plate for 1st person = arr[0] - 1 = 1 -1 = 0

So, arr = {0, 1}

One round of the permutation finished but still one plate of food is left for the 2nd person as now arr = {0, 1}. So, the process will repeat from the start.

• P2[0] = 2: 2nd person will go to the food counter and take one plate. Remaining plate for 2nd person = arr[1] - 1 = 1 -1 = 0

So, arr = {0, 0}

• P2[1] = 1: 1st person has 0 plates left to eat, so he will be skipped.

Now, none of the persons has left any number of plates to eat (as arr has become {0, 0}), so the process will stop. Three plates of food are taken from the food counter and the people reached the food counter in the following order:

{2, 1, 2}

Here we can see none of the people has got two consecutive chances to go to the food counter and take a plate. So, this permutation is a nice permutation.

So, the total number of nice permutations for N = 2 and arr = {1, 2} is 1.

Now that we understand the problem let's discuss the approach to solve it in the next section.

Also see, Euclid GCD Algorithm

## 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 xth round), 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:

1. n: Number of people in the party
2. 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

for(long long i = 1; i <= n; i++)
{
ans = (ans * i) % mod;
if (i != k + 1) {
}
}

// 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

1. 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.

2. 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.

Live masterclass