Count ways to arrange integers in circle such that no two adjacent are same
Given 2 integers N and M, find the number of ways to arrange N integers in a circle such that every integer is in the range 0 to M-1, and no two adjacent integers are same. As the answer could be large, find the number, modulo 998244353.
Examples:
Input: N=3, M=3
Output: 6
Explanation: There are six ways as follows (0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0).Input: N =4, M=2
Output: 2
Explanation: There are two ways as follows (0, 1, 0, 1), (1, 0, 1, 0).
Approach: To solve the problem, follow the below idea:
The approach effectively uses dynamic programming to build up the count of valid arrangements.
State Representation:
- dp[i][0]: stores the number of ways to arrange first i integers such that the ith integer is different from the first integer.
- dp[i][1]: stores the number of ways to arrange first i integers such that the ith integer is same as the first integer.
Base Case:
- dp[1][1] = m: There is only one element, so we can have numbers 0 to m-1 i.e. total m ways
Transitions:
- dp[i][0] += (dp[i-1][0] * (m – 2) + dp[i-1][1] * (m – 1)): If the first and the ith integer are different, then we have to take the sum of both the cases:
- The (i – 1)th integer is same as the first integer, so the number of ways will be dp[i-1][1] * (m – 1).
- The (i – 1)th integer is different from the first integer, so the number of ways will be dp[i-1][0] * (m – 2)
- dp[i][1] += dp[i – 1][0]: If the first and the ith integer are same, then the ith element should be same as the last element.
Step-by-step algorithm:
- The dynamic programming array dp[N+1][2] is used to store the number of ways for each integer.
- The base case dp[1][1] = m initializes the number of ways to assign integers to the first person.
- Construct the dp array according to the above state transitions.
- Return dp[N][0] as the final result.
Below is the implementation of the algorithm:
C++
#include <bits/stdc++.h> using namespace std; #define ll long long #define MOD 998244353 int main() { int n = 3, m = 3; vector<vector< long long >> dp(n + 1, vector< long long >(2, 0)); dp[1][0] = 0; // Initialize base case dp[1][1] = m; // Bottom-up dynamic programming to fill DP table for ( int i = 2; i <= n; i++) { // No consecutive numbers are the same dp[i][0] = (dp[i - 1][0] * (m - 2) + dp[i-1][1] * (m - 1)); dp[i][1] = dp[i - 1][0]; dp[i][0] %= MOD; dp[1][1] %= MOD; } // Output the result cout << dp[n][0]; return 0; } |
Java
import java.util.ArrayList; import java.util.List; public class Main { public static void main(String[] args) { int n = 3 , m = 3 ; List<List<Long>> dp = new ArrayList<>(n + 1 ); for ( int i = 0 ; i <= n; i++) { dp.add( new ArrayList<>(List.of(0L, 0L))); } dp.get( 1 ).set( 0 , 0L); // Initialize base case dp.get( 1 ).set( 1 , ( long ) m); // Bottom-up dynamic programming to fill DP table for ( int i = 2 ; i <= n; i++) { // No consecutive numbers are the same dp.get(i).set( 0 , (dp.get(i - 1 ).get( 0 ) * (m - 2 ) + dp.get(i - 1 ).get( 1 ) * (m - 1 )) % 998244353 ); dp.get(i).set( 1 , dp.get(i - 1 ).get( 0 ) % 998244353 ); dp.get( 1 ).set( 1 , dp.get( 1 ).get( 1 ) % 998244353 ); } // Output the result System.out.println(dp.get(n).get( 0 )); } } |
Python3
MOD = 998244353 def main(): n = 3 m = 3 # Initialize DP table dp = [[ 0 for _ in range ( 2 )] for _ in range (n + 1 )] # Initialize base case dp[ 1 ][ 0 ] = 0 dp[ 1 ][ 1 ] = m # Bottom-up dynamic programming to fill DP table for i in range ( 2 , n + 1 ): # No consecutive numbers are the same dp[i][ 0 ] = (dp[i - 1 ][ 0 ] * (m - 2 ) + dp[i - 1 ][ 1 ] * (m - 1 )) % MOD dp[i][ 1 ] = dp[i - 1 ][ 0 ] % MOD # Output the result print (dp[n][ 0 ]) if __name__ = = "__main__" : main() |
C#
using System; using System.Collections.Generic; class Program { static void Main() { int n = 3, m = 3; List<List< long > > dp = new List<List< long > >(n + 1); for ( int i = 0; i <= n; i++) { dp.Add( new List< long >( new long [2])); } dp[1][0] = 0; // Initialize base case dp[1][1] = m; // Bottom-up dynamic programming to fill DP table for ( int i = 2; i <= n; i++) { // No consecutive numbers are the same dp[i][0] = (dp[i - 1][0] * (m - 2) + dp[i - 1][1] * (m - 1)) % 998244353; dp[i][1] = dp[i - 1][0] % 998244353; dp[1][1] %= 998244353; } // Output the result Console.WriteLine(dp[n][0]); } } |
Javascript
const MOD = 998244353; function main() { const n = 3, m = 3; // Initialize dp array with dimensions (n+1) x 2 filled with 0s let dp = new Array(n + 1).fill(0).map(() => new Array(2).fill(0)); dp[1][0] = 0; // Initialize base case dp[1][1] = m; // Bottom-up dynamic programming to fill DP table for (let i = 2; i <= n; i++) { // No consecutive numbers are the same dp[i][0] = (dp[i - 1][0] * (m - 2) + dp[i-1][1] * (m - 1)) % MOD; dp[i][1] = dp[i - 1][0]; dp[i][0] %= MOD; dp[1][1] %= MOD; } // Output the result console.log(dp[n][0]); } main(); |
6
Time complexity: O(N), where N is total number of integers in the input.
Space complexity: O(N)
Contact Us