Number of ways to arrange N numbers which are in a range from 1 to K under given constraints.

0 0 8 minutes read

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

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 ways
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].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 code
int 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 ways
def 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 code
N = 5;
K = 3;
P = 2;
Q = 1;
 
# Function call
NumberOfWays(N, K, P, Q);
    

C#

// C# code implementation
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 the total 
// number of ways
function 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

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 ways
void 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 code
int 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 ways
def 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 code
N = 5
K = 3
P = 2
Q = 1
 
# Function call
NumberOfWays(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 ways
function 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 code
let N = 5;
let K = 3;
let P = 2;
let Q = 1;
 
// Function call
NumberOfWays(N, K, P, Q);

Output

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 zambiatek!