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
Naive approach: Generate all the permutations and count how many of them satisfy the given conditions.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the count// of required arrangementsint 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 codeint main(){ int n = 6; cout << countWays(n); return 0;} |
Java
// Java implementation of the // above approachimport java.util.*;class GFG{// Function to return the count// of required arrangementsstatic int countWays(int n){ // Create a vector Vector<Integer> a = new Vector<>(); int i = 1; // Store numbers from // 1 to n while (i <= n) a.add(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 boolean flag = (a.get(0) == 1); // Checking if the current // permutation satisfies the // given conditions for (int j = 1; j < n; j++) { // If the current permutation // is invalid then set the // flag to false if (Math.abs(a.get(j) - a.get(j - 1)) > 2) flag = false; } // If valid arrangement if (flag) ways++; // Generate the next permutation } while (next_permutation(a)); return ways;} static boolean next_permutation(Vector<Integer> p) { for (int a = p.size() - 2; a >= 0; --a) if (p.get(a) < p.get(a + 1)) for (int b = p.size() - 1;; --b) if (p.get(b) > p.get(a)) { int t = p.get(a); p.set(a, p.get(b)); p.set(b, t); for (++a, b = p.size() - 1; a < b; ++a, --b) { t = p.get(a); p.set(a, p.get(b)); p.set(b, t); } return true; } return false;}// Driver codepublic static void main(String[] args){ int n = 6; System.out.print(countWays(n));}}// This code is contributed by shikhasingrajput |
Python3
# Python3 implementation of the approachfrom itertools import permutations # Function to return the count# of required arrangementsdef countWays(n): # Create a vector a = [] i = 1 # Store numbers from 1 to n while (i <= n): a.append(i) i += 1 # To store the count of ways ways = 0 # Generate the all permutation for per in list(permutations(a)): # Initialize flag to true if first # element is 1 else false flag = 1 if (per[0] == 1) else 0 # Checking if the current permutation # satisfies the given conditions for i in range(1, n): # If the current permutation is invalid # then set the flag to false if (abs(per[i] - per[i - 1]) > 2): flag = 0 # If valid arrangement if (flag): ways += 1 return ways # Driver coden = 6print(countWays(n))# This code is contributed by shivanisinghss2110 |
C#
// C# implementation of the // above approachusing System;using System.Collections.Generic;class GFG{// Function to return the count// of required arrangementsstatic int countWays(int n){ // Create a vector List<int> a = new List<int>(); int i = 1; // Store numbers from // 1 to n while (i <= n) a.Add(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 j = 1; j < n; j++) { // If the current permutation // is invalid then set the // flag to false if (Math.Abs(a[j] - a[j - 1]) > 2) flag = false; } // If valid arrangement if (flag) ways++; // Generate the next // permutation } while (next_permutation(a)); return ways;} static bool next_permutation(List<int> p) { for (int a = p.Count - 2; a >= 0; --a) if (p[a] < p[a + 1]) for (int b = p.Count - 1;; --b) if (p[b] > p[a]) { int t = p[a]; p[a] = p[b]; p[b] = t; for (++a, b = p.Count - 1; a < b; ++a, --b) { t = p[a]; p[a] = p[b]; p[b] = t; } return true; } return false;}// Driver codepublic static void Main(String[] args){ int n = 6; Console.Write(countWays(n));}}// This code is contributed by Rajput-Ji |
Javascript
<script>// Javascript implementation of the// above approach// Function to return the count// of required arrangementsfunction countWays(n){ // Create a vector let a =[]; let i = 1; // Store numbers from // 1 to n while (i <= n) a.push(i++); // To store the count // of ways let ways = 0; // Generate all the permutations // using next_permutation in STL do { // Initialize flag to true // if first element is 1 // else false let flag = (a[0] == 1); // Checking if the current // permutation satisfies the // given conditions for (let j = 1; j < n; j++) { // If the current permutation // is invalid then set the // flag to false if (Math.abs(a[j] - a[j - 1]) > 2) flag = false; } // If valid arrangement if (flag) ways++; // Generate the next permutation } while (next_permutation(a)); return ways;}function next_permutation(p){ for (let a = p.length - 2;a >= 0; --a) {if (p[a] < p[a + 1]) {for (let b = p.length - 1;; --b) {if (p[b] > p[a]) { let t = p[a]; p[a] = p[b]; p[b] = t; for (++a, b = p.length - 1; a < b; ++a, --b) { t = p[a]; p[a] = p[b]; p[b] = t; } return true; } } } } return false;}// Driver codelet n = 6;document.write(countWays(n));// This code is contributed by patel2127</script> |
Output:
9
Efficient approach: This problem can be solved using dynamic 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:
- 12_____ – “2” in the second position.
- 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. - 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:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the count// of required arrangementsint 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 codeint main(){ int n = 6; cout << countWays(n); return 0;} |
Java
// Java implementation of the approachclass GFG{// Function to return the count// of required arrangementsstatic int countWays(int n){ // Create the dp array int []dp = new int[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 codepublic static void main(String args[]) { int n = 6; System.out.println(countWays(n));}}// This code is contributed by 29AjayKumar |
Python3
# Python implementation of the approach# Function to return the count# of required arrangementsdef countWays(n): # Create the dp array dp = [0 for i in range(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 i in range(3, n + 1): dp[i] = dp[i - 1] + dp[i - 3] + 1 # dp[n] contains the desired answer return dp[n]# Driver coden = 6print(countWays(n))# This code is contributed by Mohit Kumar |
C#
// C# implementation of the approachusing System;class GFG{// Function to return the count// of required arrangementsstatic int countWays(int n){ // Create the dp array int []dp = new int[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 codepublic static void Main() { int n = 6; Console.WriteLine(countWays(n));}}// This code is contributed by Code@Mech. |
Javascript
<script>// Function to return the count// of required arrangementsfunction countWays( n){ // Create the dp array let dp = new Array (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 (let 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 let n = 6; document.write(countWays(n)); // This code is contributed by shivanisinghss2110</script> |
Output:
9
Time Complexity: O(N)
Space Complexity: O(N)
Efficient approach : Space optimization O(1)
In previous approach the current value dp[i] is depend upon the previous 2 values i.e. dp[i-1] and dp[i-3] so instead of using array of size N we can create 3 variables prev1 , prev2, prev3 to keep track of previous 3 computations.
Implementations Steps :
- Create variables prev1, prev2, prev3 to store previous computations.
- Initialize them with base cases.
- Create a variable curr to store current value.
- Now iterate over subproblems and get the current value from previous values.
- After every iteration update prev1, prev2 and prev3 for further iterations.
- At last return final answer.
Implementation:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the count// of required arrangementsint countWays(int n){ // Initialize the base cases // as explained above int prev1 =0; int prev2 =1; int prev3 =1; // to store current value int curr; // Generate answer for greater values for (int i = 3; i <= n; i++) { curr = prev3 + prev1 + 1; // assigning values for further iterations prev1 = prev2; prev2=prev3; prev3=curr; } // curr contains the desired answer return curr;}// Driver codeint main(){ int n = 6; // function call cout << countWays(n); return 0;} |
Python3
# Python implementation of the# aforementioned approachdef countWays(n): # Initializing 3 variables # prev1 = 0 # prev2 = 1 # prev3 = 1 prev1, prev2, prev3 = 0, 1, 1 # Running a loop from 3 to n for i in range(3, n+1): # using variable curr to store # the recent value curr = prev3+prev1+1 # assigning values for further iterations prev1 = prev2 prev2 = prev3 prev3 = curr return curr# Driver Coden = 6print(countWays(n)) |
Javascript
// Function to return the count// of required arrangementsfunction countWays(n) { // Initialize the base cases // as explained above let prev1 = 0; let prev2 = 1; let prev3 = 1; // to store current value let curr; // Generate answer for greater values for (let i = 3; i <= n; i++) { curr = prev3 + prev1 + 1; // assigning values for further iterations prev1 = prev2; prev2 = prev3; prev3 = curr; } // curr contains the desired answer return curr;}// Driver codelet n = 6;// function callconsole.log(countWays(n)); |
Java
// Java implementation of the approachimport java.util.*;class Main { // Function to return the count // of required arrangements public static int countWays(int n) { // Initialize the base cases // as explained above int prev1 = 0; int prev2 = 1; int prev3 = 1; // to store current value int curr = 0; // Generate answer for greater values for (int i = 3; i <= n; i++) { curr = prev3 + prev1 + 1; // assigning values for further iterations prev1 = prev2; prev2 = prev3; prev3 = curr; } // curr contains the desired answer return curr; } // Driver code public static void main(String[] args) { int N = 6; System.out.print(countWays(N)); }} |
C#
using System;public class MainClass { // Driver Code public static void Main() { int n = 6; // Initialize the base cases // as explained above int prev1 = 0; int prev2 = 1; int prev3 = 1; int curr = 0; // Generate answer for greater values for (int i = 3; i <= n; i++) { curr = prev3 + prev1 + 1; // Assigning values for // further iterations prev1 = prev2; prev2 = prev3; prev3 = curr; } // curr contains desired answer Console.WriteLine(curr); }} |
Output
9
Time Complexity: O(N)
Space Complexity: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
