# 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

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 == 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  a = 1  a = 1
```

Below is the implementation of the above approach:

filter_none

edit

close

play_arrow

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;`
`  ` `dp = 1;`
` `
`  ` `// (12) as the only possibility`
`  ` `dp = 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;`
`}`