Given two integer N and M, the task is to find the count of arrays of size N with elements from the range [1, M] in which all subarrays of length greater than 1 can be made palindromic by replacing less than half of its elements i.e., floor(length/2).
Examples:
Input: N = 2, M = 3
Output: 6
Explanation:
There are 9 arrays possible of length 2 using values 1 to 3 i.e. [1, 1], [1, 2], [1, 3], [2, 1][2, 2], [2, 3], [3, 1], [3, 2], [3, 3].
All of these arrays except [1, 1], [2, 2] and [3, 3] have subarrays of length greater than 1 which requires 1 operation to make them palindrome. So the required answer is 9 – 3 = 6.Input: N = 5, M = 10
Output: 30240
Approach: The problem can be solved based on the following observations:
- It is possible that the maximum permissible number of operations required to make an array a palindrome is floor(size(array)/2).
- It can be observed that by choosing a subarray, starting and ending with the same value, the number of operations needed to make it a palindrome will be less than floor(size of subarray)/2.
- Therefore, the task is reduced to finding the number of arrays of size N using integer values in the range [1, M], which do not contain any duplicate elements, which can be easily done by finding the permutation of M with N i.e. MpN, which is equal to M * (M – 1) * (M – 2) * … * (M – N + 1).
Follow the steps below to solve the problem:
- Initialize an integer variable, say ans = 1.
- Traverse from i = 0 to N – 1 and update ans as ans = ans * (M-i)
- Print ans as the answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;typedef long long ll;// Function to find the number of arrays// following the given conditionvoid noOfArraysPossible(ll N, ll M){ // Initialize answer ll ans = 1; // Calculate nPm for (ll i = 0; i < N; ++i) { ans = ans * (M - i); } // Print ans cout << ans;}// Driver Codeint main(){ // Given N and M ll N = 2, M = 3; // Function Call noOfArraysPossible(N, M); return 0;} |
Java
// Java program for the above approachclass GFG{// Function to find the number of arrays// following the given conditionstatic void noOfArraysPossible(int N, int M){ // Initialize answer int ans = 1; // Calculate nPm for (int i = 0; i < N; ++i) { ans = ans * (M - i); } // Print ans System.out.print(ans);}// Driver Codepublic static void main(String[] args){ // Given N and M int N = 2, M = 3; // Function Call noOfArraysPossible(N, M);}}// This code is contributed by Princi Singh |
Python3
# Python3 program for the above approach# Function to find the number of arrays# following the given conditiondef noOfArraysPossible(N, M): # Initialize answer ans = 1 # Calculate nPm for i in range(N): ans = ans * (M - i) # Print ans print(ans) # Driver Codeif __name__ == "__main__" : # Given N and M N = 2 M = 3 # Function Call noOfArraysPossible(N, M) # This code is contributed by jana_sayantan |
C#
// C# program to implement// the above approach using System;class GFG{ // Function to find the number of arrays// following the given conditionstatic void noOfArraysPossible(int N, int M){ // Initialize answer int ans = 1; // Calculate nPm for (int i = 0; i < N; ++i) { ans = ans * (M - i); } // Print ans Console.Write(ans);} // Driver Codepublic static void Main(){ // Given N and M int N = 2, M = 3; // Function Call noOfArraysPossible(N, M);}}// This code is contributed by susmitakundugoaldanga |
Javascript
<script>// javascript program for the above approach // Function to find the number of arrays // following the given condition function noOfArraysPossible(N , M) { // Initialize answer var ans = 1; // Calculate nPm for (i = 0; i < N; ++i) { ans = ans * (M - i); } // Print ans document.write(ans); } // Driver Code // Given N and M var N = 2, M = 3; // Function Call noOfArraysPossible(N, M);// This code is contributed by todaysgaurav </script> |
6
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!