Given Four integers N, K, P and Q. The task is to calculate the number of ways to arrange N numbers which are in a range from 1 to K such that the first number is P, the last number is Q and no two adjacent numbers are consecutive.
Examples:
Input: N = 4, K = 3, P = 2, Q = 3 Output: 3 Explanation: For N=4, K=3, P=2, Q=3, ways are [2, 1, 2, 3], [2, 3, 1, 3], [2, 3, 2, 3] Input: N = 5, K = 3, P = 2, Q = 1 Output: 5
Approach: The idea is to use Dynamic Programming to solve this problem.
- Let’s try to understand this by taking an example, N = 4, K = 3, P = 2, Q = 1.
We will observe all possible arrangements starting from P and try to find any pattern that can be useful to apply Dynamic programming.
- Below is the image showing all possible arrangements starting from P = 2.
- Let A be the array that consists of the number of nodes ending at Q at a particular level
A = { 0, 1, 1, 3 }
Let B be the array that consists of the number of nodes NOT ending at Q at a particular level
B = {1, 1, 3, 5 } - On careful observation it may be noted that:
- A[i] = B[i-1]
Reason :
All the favourable nodes ( ending at Q ) will only be produced by non-favourable nodes(NOT ending at Q) of the previous level.
- B[i] = A[i-1]*(K – 1) + B[i-1]*(K – 2)
Reason :- For A[i-1]*(K – 1), some of the non-favourable nodes are produced by favourable nodes of the previous level, multiply by (K – 1) as each favourable node will produce K-1 non-favourable nodes
- For B[i-1]*(K – 2), rest of the non-favourable nodes are produced by non-favourable nodes of the previous level, multiply by (K-2), as one produced node is favourable, so we subtract 2 from this.
- For A[i-1]*(K – 1), some of the non-favourable nodes are produced by favourable nodes of the previous level, multiply by (K – 1) as each favourable node will produce K-1 non-favourable nodes
- A[i] = B[i-1]
C++
// C++ program to calculate Number of // ways to arrange N numbers under// given constraints.#include <bits/stdc++.h>using namespace std;class element {public: // For favourable nodes // (ending at Q) int A; // For Non-favourable nodes // (NOT ending at Q) int B;};// Function to print Total number// of waysvoid NumberOfWays(int n, int k, int p, int q){ element* dp = new element[n]; // If the First number and the // last number is same. if (p == q) { dp[0].A = 1; dp[0].B = 0; } else { dp[0].A = 0; dp[0].B = 1; } // DP approach to find current state // with the help of previous state. for (int i = 1; i < n; i++) { dp[i].A = dp[i - 1].B; dp[i].B = (dp[i - 1].A * (k - 1)) + (dp[i - 1].B * (k - 2)); } cout << dp[n - 1].A << endl; return;}// Driver codeint main(){ int N = 5; int K = 3; int P = 2; int Q = 1; // Function call NumberOfWays(N, K, P, Q);} |
Java
// Java program to calculate number of // ways to arrange N numbers under // given constraints. import java.io.*;import java.util.*; class GFG{// Function to print Total number // of ways static void NumberOfWays(int n, int k, int p, int q) { int[][] dp = new int[n][2]; // If the First number and the // last number is same. if (p == q) { dp[0][0] = 1; dp[0][1] = 0; } else { dp[0][0] = 0; dp[0][1] = 1; } // DP approach to find current state // with the help of previous state. for(int i = 1; i < n; i++) { dp[i][0] = dp[i - 1][1]; dp[i][1] = (dp[i - 1][0] * (k - 1)) + (dp[i - 1][1] * (k - 2)); } System.out.println(dp[n - 1][0]); } // Driver Code public static void main(String args[]) { int N = 5; int K = 3; int P = 2; int Q = 1; // Function call NumberOfWays(N, K, P, Q); }} // This code is contributed by offbeat |
Python3
# Python program to calculate Number of # ways to arrange N numbers under# given constraints.class element: def __init__(self, A, B): # For favourable nodes # (ending at Q) self.A = A # For Non-favourable nodes # (NOT ending at Q) self.B = B# Function to print Total number# of waysdef NumberOfWays( n, k, p, q): dp = []; # If the First number and the # last number is same. if (p == q): dp.append(element(1,0)) else: dp.append(element(0,1)) # DP approach to find current state # with the help of previous state. for i in range(1,n): dp.append(element(dp[i-1].B,(dp[i - 1].A * (k - 1)) + (dp[i - 1].B * (k - 2)))) print(dp[n - 1].A); return;# Driver codeN = 5;K = 3;P = 2;Q = 1;# Function callNumberOfWays(N, K, P, Q); |
C#
// C# code implementationusing System;public class Element{ // For favourable nodes // (ending at Q) public int A { get; set; } // For Non-favourable nodes // (NOT ending at Q) public int B { get; set; }}public class Program{ // Function to print Total number // of ways public static void NumberOfWays(int n, int k, int p, int q) { Element[] dp = new Element[n]; // If the First number and the // last number is same. if (p == q) { dp[0] = new Element { A = 1, B = 0 }; } else { dp[0] = new Element { A = 0, B = 1 }; } // DP approach to find current state // with the help of previous state. for (int i = 1; i < n; i++) { dp[i] = new Element { A = dp[i - 1].B, B = (dp[i - 1].A * (k - 1)) + (dp[i - 1].B * (k - 2)) }; } Console.WriteLine(dp[n - 1].A); } // Driver code public static void Main() { int N = 5; int K = 3; int P = 2; int Q = 1; // Function call NumberOfWays(N, K, P, Q); }} |
Javascript
// Function to print the total // number of waysfunction NumberOFWays(n, k, p, q){ dp = []; for(let i = 0; i < n; i++){ dp.push([0, 0]); } // If the first number and the // last number is same. if(p == q){ dp[0][0] = 1; dp[0][1] = 0; } else{ dp[0][0] = 0; dp[0][1] = 1; } // DP approach to find current state // with help of previous state for(let i = 1; i < n; i++){ dp[i][0] = dp[i-1][1]; dp[i][1] = (dp[i-1][0]*(k-1)) + (dp[i-1][1]*(k-2)); } console.log(dp[n-1][0]);}// Driver code let N = 5;let K = 3;let P = 2;let Q = 1;// Function call NumberOFWays(N, K, P, Q);// This code is contributed By Aditya Sharma |
Output
5
Time Complexity: O(N).
Auxiliary Space: O(N)
Efficient approach : space optimization O(1)
In previous approach dp[i] is depend only upon dp[i-1] so we can replace these dp[i] to curr and dp[i-1] to prev to determine the current and previous computation.
Implementation Steps:
- Take two variables prev_A and prev_B to keep track of previous 2 numbers and curr_A and curr_B for current two numbers.
- Initialize prev_A and prev_B by checking first and last numbers are same or not.
- Now iterate over subproblems to determine curr_A and curr_B from previous computations.
- At last return answer stored in curr_A.
Implementation:
C++
// C++ program to calculate Number of// ways to arrange N numbers under// given constraints.#include <bits/stdc++.h>using namespace std;// Function to print Total number// of waysvoid NumberOfWays(int n, int k, int p, int q){ int prev_A, prev_B; // If the First number and the // last number is same. if (p == q) { prev_A = 1; prev_B = 0; } else { prev_A = 0; prev_B = 1; } int curr_A, curr_B; // DP approach to find current state // with the help of previous state. for (int i = 1; i < n; i++) { curr_A = prev_B; curr_B = (prev_A * (k - 1)) + (prev_B * (k - 2)); prev_A = curr_A; prev_B = curr_B; } cout << curr_A << endl; return;}// Driver codeint main(){ int N = 5; int K = 3; int P = 2; int Q = 1; // Function call NumberOfWays(N, K, P, Q);} |
Java
import java.util.*;class Main { // Function to print Total number // of ways static void numberOfWays(int n, int k, int p, int q) { int prevA, prevB; // If the First number and the // last number is same. if (p == q) { prevA = 1; prevB = 0; } else { prevA = 0; prevB = 1; } int currA = 0; int currB = 0; // DP approach to find current state // with the help of previous state. for (int i = 1; i < n; i++) { currA = prevB; currB = (prevA * (k - 1)) + (prevB * (k - 2)); prevA = currA; prevB = currB; } System.out.println(currA); return; } // Driver code public static void main(String[] args) { int N = 5; int K = 3; int P = 2; int Q = 1; // Function call numberOfWays(N, K, P, Q); }} |
Python
# Python program to calculate Number of# ways to arrange N numbers under# given constraints.# Function to print Total number# of waysdef NumberOfWays(n, k, p, q): # If the First number and the # last number is same. if p == q: prev_A = 1 prev_B = 0 else: prev_A = 0 prev_B = 1 # DP approach to find current state # with the help of previous state. for i in range(1, n): curr_A = prev_B curr_B = (prev_A * (k - 1)) + (prev_B * (k - 2)) prev_A = curr_A prev_B = curr_B print(curr_A)# Driver codeN = 5K = 3P = 2Q = 1# Function callNumberOfWays(N, K, P, Q) |
C#
using System;public class Element{ // For favourable nodes // (ending at Q) public int A { get; set; } // For Non-favourable nodes // (NOT ending at Q) public int B { get; set; }}public class Program{ // Function to print Total number // of ways public static void NumberOfWays(int n, int k, int p, int q) { Element[] dp = new Element[n]; // If the First number and the // last number is same. if (p == q) { dp[0] = new Element { A = 1, B = 0 }; } else { dp[0] = new Element { A = 0, B = 1 }; } // DP approach to find current state // with the help of previous state. for (int i = 1; i < n; i++) { dp[i] = new Element { A = dp[i - 1].B, B = (dp[i - 1].A * (k - 1)) + (dp[i - 1].B * (k - 2)) }; } Console.WriteLine(dp[n - 1].A); } // Driver code public static void Main() { int N = 5; int K = 3; int P = 2; int Q = 1; // Function call NumberOfWays(N, K, P, Q); }} |
Javascript
// Function to print Total number of waysfunction NumberOfWays(n, k, p, q) { // If the First number and the last number is same. let prev_A, prev_B; if (p == q) { prev_A = 1; prev_B = 0; } else { prev_A = 0; prev_B = 1; } // DP approach to find current state // with the help of previous state. for (let i = 1; i < n; i++) { let curr_A = prev_B; let curr_B = (prev_A * (k - 1)) + (prev_B * (k - 2)); prev_A = curr_A; prev_B = curr_B; } console.log(prev_A);}// Driver codelet N = 5;let K = 3;let P = 2;let Q = 1;// Function callNumberOfWays(N, K, P, Q); |
Output
5
Time Complexity: O(N).
Auxiliary Space: 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!
