Count number of ways to arrange first N numbers

Count number of ways to arrange the first N natural numbers in a line such that the left-most number is always 1 and no two consecutive numbers have an absolute difference greater than 2 .

Examples:

Input:N = 4

Output:4

The only possible arrangements are (1, 2, 3, 4),

(1, 2, 4, 3), (1, 3, 4, 2) and (1, 3, 2, 4).

Input:N = 6

Output:9

Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Naive approach:Generate all the permutations and count how many of them satisfy the given conditions.

Below is the implementation of the above approach:

filter_none

edit

close

play_arrow

link

brightness_4

code

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the count
// of required arrangements
int countWays( int n)
{
 
   // Create a vector
   vector< int > a;
   int i = 1;
 
   // Store numbers from 1 to n
   while (i <= n)
     a.push_back(i++);
 
   // To store the count of ways
   int ways = 0;
 
   // Generate all the permutations
   // using next_permutation in STL
   do {
     // Initialize flag to true if first
     // element is 1 else false
     bool flag = (a[0] == 1);
 
     // Checking if the current permutation
     // satisfies the given conditions
     for ( int i = 1; i < n; i++) {
 
       // If the current permutation is invalid
       // then set the flag to false
       if ( abs (a[i] - a[i - 1]) > 2)
         flag = 0;
     }
 
     // If valid arrangement
     if (flag)
       ways++;
 
     // Generate the next permutation
   } while (next_permutation(a.begin(), a.end()));
 
   return ways;
}
 
// Driver code
int main()
{
   int n = 6;
 
   cout << countWays(n);
 
   return 0;
}

chevron_right

filter_none

Output:

Efficient approach:This problem can be solved usingdynamic programming.

A better linear approach to this problem relies on the following observation. Look for the position of 2. Let a[i] be the number of ways for n = i. There are three cases:

  1. 12_____ – “2” in the second position.
  2. 1*2____ – “2” in the third position.
    1**2___ – “2” in the fourth position is impossible because only possible way is (1342), which is same as case 3.
    1***2__ – “2” in the fifth position is impossible because 1 must be followed by 3 , 3 by 5 and 2 needs 4 before it so it becomes 13542 , again as case 3.
  3. 1_(i – 2)terms___2 – “2” in the last position (1357642 and similar)

For each case, the following are the sub-task:

Adding 1 to each term of a[i – 1] i.e. (1__(i – 1) terms__).

As for 1_2_____ there can only be one 1324___(i – 4) terms____ i.e. a[i – 3].

Hence, the recurrence relation will be,

 a[i] = a[i – 1] + a[i – 3] + 1 

And the base cases will be:

 a[0] = 0  a[1] = 1  a[2] = 1 

Below is the implementation of the above approach:

filter_none

edit

close

play_arrow

link

brightness_4

code

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the count
// of required arrangements
int countWays( int n)
{
   // Create the dp array
   int dp[n + 1];
 
   // Initialize the base cases
   // as explained above
   dp[0] = 0;
   dp[1] = 1;
 
   // (12) as the only possibility
   dp[2] = 1;
 
   // Generate answer for greater values
   for ( int i = 3; i <= n; i++) {
     dp[i] = dp[i - 1] + dp[i - 3] + 1;
   }
 
   // dp[n] contains the desired answer
   return dp[n];
}
 
// Driver code
int main()
{
   int n = 6;
 
   cout << countWays(n);
 
   return 0;
}
我来评几句
登录后评论

已发表评论数()

相关站点

+订阅
热门文章