Given two integers M and N, the task is to find the number of N-length arrays possible having non-equal adjacent elements lying in the range [1, M] having elements at first and last indices equal.
Examples:
Input: N = 3, M = 3
Output: 6
Explanation:
The possible arrays are {1, 2, 1}, {1, 3, 1}, {2, 1, 2}, {2, 3, 2}, {3, 1, 3}, {3, 2, 3}.Input: N = 5, M = 4
Output: 84
Approach: Follow the steps below to solve the problem:
- First fix arr[0] and arr[N-1] equal to 1.
- Now find the number of arrays possible of size i which ends with 1 (i.e., arr[i] = 1). Store this result into end_with_one[i].
- Now, find the number of arrays possible of size i which does not end with 1 (arr[i] ? 1). Store this result into end_not_with_one[i].
- Since, the number of ways to form the array till the ith index with arr[i] = 1, is same as the number of ways to form the array till the (i – 1)th index with arr[i – 1] ? 1, set end_with_one[i] = end_not_with_one[i – 1].
- Now, the number of ways to form the array till the ith index with arr[i] ? 1 is as follows:
- If arr[i – 1]= 1, there are (M – 1) numbers to be placed at the ith index.
- If arr[i – 1] ? 1, then (M – 2) numbers can be placed at index i, since arr[i] cannot be 1 and arr[i] cannot be equal to arr[i – 1].
- Therefore, set end_not_with_one[i] = end_with_one[i-1] * (M – 1) + end_not_with_one[i-1]* (M – 2).
- Therefore, the number of ways to form arrays of size N with arr[0] and arr[N – 1] equal to 1 is end_with_one[N – 1].
- Similarly, arr[0] and arr[N – 1] can be set to any element from 1 to M.
- Therefore, the total number of arrays possible is M * end_with_one[N-1].
Below is the implementation of the above approach:
C++14
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to print the count of// arrays satisfying given conditionint totalArrays(int N, int M){ int end_with_one[N + 1]; int end_not_with_one[N + 1]; // First element of // array is set as 1 end_with_one[0] = 1; end_not_with_one[0] = 0; // Since the first element // of arr[] is 1, the // second element can't be 1 end_with_one[1] = 0; end_not_with_one[1] = M - 1; // Traverse the remaining indices for (int i = 2; i < N; i++) { // If arr[i] = 1 end_with_one[i] = end_not_with_one[i - 1]; // If arr[i] ? 1 end_not_with_one[i] = end_with_one[i - 1] * (M - 1) + end_not_with_one[i - 1] * (M - 2); } // Since last element needs to be 1 return end_with_one[N - 1];}// Driver Codeint main(){ int N = 3, M = 3; // Stores the count of arrays // where arr[0] = arr[N - 1] = 1 int temp = totalArrays(N, M); // Since arr[0] and arr[N - 1] // can be any number from 1 to M int ans = M * temp; // Print answer cout << ans << "\n"; return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to print the count of// arrays satisfying given conditionstatic int totalArrays(int N, int M){ int []end_with_one = new int[N + 1]; int []end_not_with_one = new int[N + 1]; // First element of // array is set as 1 end_with_one[0] = 1; end_not_with_one[0] = 0; // Since the first element // of arr[] is 1, the // second element can't be 1 end_with_one[1] = 0; end_not_with_one[1] = M - 1; // Traverse the remaining indices for (int i = 2; i < N; i++) { // If arr[i] = 1 end_with_one[i] = end_not_with_one[i - 1]; // If arr[i] ? 1 end_not_with_one[i] = end_with_one[i - 1] * (M - 1) + end_not_with_one[i - 1] * (M - 2); } // Since last element needs to be 1 return end_with_one[N - 1];}// Driver Codepublic static void main(String[] args){ int N = 3, M = 3; // Stores the count of arrays // where arr[0] = arr[N - 1] = 1 int temp = totalArrays(N, M); // Since arr[0] and arr[N - 1] // can be any number from 1 to M int ans = M * temp; // Print answer System.out.print(ans+ "\n");}}// This code is contributed by 29AjayKumar |
Python3
# Python program for the above approach# Function to print the count of# arrays satisfying given conditiondef totalArrays(N, M): end_with_one = [0] * (N + 1); end_not_with_one = [0] * (N + 1); # First element of # array is set as 1 end_with_one[0] = 1; end_not_with_one[0] = 0; # Since the first element # of arr is 1, the # second element can't be 1 end_with_one[1] = 0; end_not_with_one[1] = M - 1; # Traverse the remaining indices for i in range(2, N): # If arr[i] = 1 end_with_one[i] = end_not_with_one[i - 1]; # If arr[i] ? 1 end_not_with_one[i] = end_with_one[i - 1] * (M - 1) + end_not_with_one[i - 1] * (M - 2); # Since last element needs to be 1 return end_with_one[N - 1];# Driver Codeif __name__ == '__main__': N = 3; M = 3; # Stores the count of arrays # where arr[0] = arr[N - 1] = 1 temp = totalArrays(N, M); # Since arr[0] and arr[N - 1] # can be any number from 1 to M ans = M * temp; # Print answer print(ans); # This code is contributed by 29AjayKumar |
C#
// C# program for the above approach using System;using System.Collections.Generic;class GFG { // Function to print the count of // arrays satisfying given condition static int totalArrays(int N, int M) { int[] end_with_one = new int[N + 1]; int[] end_not_with_one = new int[N + 1]; // First element of // array is set as 1 end_with_one[0] = 1; end_not_with_one[0] = 0; // Since the first element // of arr[] is 1, the // second element can't be 1 end_with_one[1] = 0; end_not_with_one[1] = M - 1; // Traverse the remaining indices for (int i = 2; i < N; i++) { // If arr[i] = 1 end_with_one[i] = end_not_with_one[i - 1]; // If arr[i] ? 1 end_not_with_one[i] = end_with_one[i - 1] * (M - 1) + end_not_with_one[i - 1] * (M - 2); } // Since last element needs to be 1 return end_with_one[N - 1]; } // Driver code static void Main() { int N = 3, M = 3; // Stores the count of arrays // where arr[0] = arr[N - 1] = 1 int temp = totalArrays(N, M); // Since arr[0] and arr[N - 1] // can be any number from 1 to M int ans = M * temp; // Print answer Console.WriteLine(ans); }}// This code is contributed by divyeshrabadiya07 |
Javascript
<script>// Javascript program for the above approach// Function to print the count of// arrays satisfying given conditionfunction totalArrays(N, M){ var end_with_one = Array(N+1); var end_not_with_one = Array(N+1); // First element of // array is set as 1 end_with_one[0] = 1; end_not_with_one[0] = 0; // Since the first element // of arr[] is 1, the // second element can't be 1 end_with_one[1] = 0; end_not_with_one[1] = M - 1; // Traverse the remaining indices for (var i = 2; i < N; i++) { // If arr[i] = 1 end_with_one[i] = end_not_with_one[i - 1]; // If arr[i] ? 1 end_not_with_one[i] = end_with_one[i - 1] * (M - 1) + end_not_with_one[i - 1] * (M - 2); } // Since last element needs to be 1 return end_with_one[N - 1];}// Driver Codevar N = 3, M = 3;// Stores the count of arrays// where arr[0] = arr[N - 1] = 1var temp = totalArrays(N, M);// Since arr[0] and arr[N - 1]// can be any number from 1 to Mvar ans = M * temp;// Print answerdocument.write( ans + "<br>");</script> |
Output:
6
Time Complexity: O(N)
Auxiliary Space: O(N)
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!
