Given an array arr[] consisting of N integers in the range [0, M] and an integer M, the task is to count the number of ways to replace all array elements whose value is 0 with non-zero values from the range [0, M] such that all possible M consecutive elements are distinct.
Examples:
Input: arr[] = { 1, 0, 3, 0, 0 }, M = 4
Output: 2
Explanation:
Possible ways to replace arr[1], arr[3] and arr[4] with non-zero values such that no M( = 4) consecutive elements contains any duplicate elements are { { 1, 2, 3, 4, 1 }, { 1, 4, 3, 2, 1 } }.
Therefore, the required output is 2.Input: arr[] = {0, 1, 2, 1, 0}, M = 4
Output: 0
Explanation:No such arrangements possible.
Approach: The idea is to replace 0s with non-zero elements such that arr[i] must be equal to arr[i % M]. Follow the steps below to solve the problem:
- Initialize an array B[] of size M + 1, to store M consecutive array array elements such that arr[i] is equal to B[i % M].
- Traverse the array and check the following conditions:
- If arr[i] is not 0 and B[i % M] is 0, then B[i % M] will be equal to arr[i] as this number should be present as it is.
- If arr[i] is not equal to B[i % M], then print 0 as there exist no such arrangements.
- Calculate the count of 0s in the array B[], say X.
- Then, there exist factorial X possible arrangements, therefore, print the value of factorial X .
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Modular function// to calculate factoriallong long int Fact(int N){ // Stores factorial of N long long int result = 1; // Iterate over the range [1, N] for (int i = 1; i <= N; i++) { // Update result result = (result * i); } return result;}// Function to count ways to replace array// elements having 0s with non-zero elements// such that any M consecutive elements are distinctvoid numberOfWays(int M, int arr[], int N){ // Store m consecutive distinct elements // such that arr[i] is equal to B[i % M] int B[M] = { 0 }; // Stores frequency of array elements int counter[M + 1] = { 0 }; // Traverse the array arr[] for (int i = 0; i < N; i++) { // If arr[i] is non-zero if (arr[i] != 0) { // If B[i % M] is equal to 0 if (B[i % M] == 0) { // Update B[i % M] B[i % M] = arr[i]; // Update frequency of arr[i] counter[arr[i]]++; // If a duplicate element found // in M consecutive elements if (counter[arr[i]] > 1) { cout << 0 << endl; return; } } // Handling the case of // inequality else if (B[i % M] != arr[i]) { cout << 0 << endl; return; } } } // Stores count of 0s // in B[] int cnt = 0; // Traverse the array, B[] for (int i = 0; i < M; i++) { // If B[i] is 0 if (B[i] == 0) { // Update cnt cnt++; } } // Calculate factorial cout << Fact(cnt) << endl;}// Driver Codeint main(){ // Given M int M = 4; // Given array int arr[] = { 1, 0, 3, 0, 0 }; // Size of the array int N = sizeof(arr) / sizeof(arr[0]); // Function Call numberOfWays(M, arr, N);} |
Java
// Java program for the above approachimport java.io.*;class GFG{// Modular function// to calculate factorialstatic int Fact(int N){ // Stores factorial of N int result = 1; // Iterate over the range [1, N] for(int i = 1; i <= N; i++) { // Update result result = (result * i); } return result;}// Function to count ways to replace array// elements having 0s with non-zero elements// such that any M consecutive elements are distinctstatic void numberOfWays(int M, int[] arr, int N){ // Store m consecutive distinct elements // such that arr[i] is equal to B[i % M] int[] B = new int[M]; // Stores frequency of array elements int[] counter = new int[M + 1]; // Traverse the array arr[] for(int i = 0; i < N; i++) { // If arr[i] is non-zero if (arr[i] != 0) { // If B[i % M] is equal to 0 if (B[i % M] == 0) { // Update B[i % M] B[i % M] = arr[i]; // Update frequency of arr[i] counter[arr[i]]++; // If a duplicate element found // in M consecutive elements if (counter[arr[i]] > 1) { System.out.println(0); return; } } // Handling the case of // inequality else if (B[i % M] != arr[i]) { System.out.println(0); return; } } } // Stores count of 0s // in B[] int cnt = 0; // Traverse the array, B[] for(int i = 0; i < M; i++) { // If B[i] is 0 if (B[i] == 0) { // Update cnt cnt++; } } // Calculate factorial System.out.println(Fact(cnt));}// Driver Codepublic static void main(String[] args){ // Given M int M = 4; // Given array int[] arr = new int[]{ 1, 0, 3, 0, 0 }; // Size of the array int N = arr.length; // Function Call numberOfWays(M, arr, N);}}// This code is contributed by Dharanendra L V |
Python3
# Python3 program for the above approach# Modular function# to calculate factorialdef Fact(N): # Stores factorial of N result = 1 # Iterate over the range [1, N] for i in range(1, N + 1): # Update result result = (result * i) return result# Function to count ways to replace array# elements having 0s with non-zero elements# such that any M consecutive elements are distinctdef numberOfWays(M, arr, N): # Store m consecutive distinct elements # such that arr[i] is equal to B[i % M] B = [0] * (M) # Stores frequency of array elements counter = [0] * (M + 1) # Traverse the array arr for i in range(0, N): # If arr[i] is non-zero if (arr[i] != 0): # If B[i % M] is equal to 0 if (B[i % M] == 0): # Update B[i % M] B[i % M] = arr[i] # Update frequency of arr[i] counter[arr[i]] += 1 # If a duplicate element found # in M consecutive elements if (counter[arr[i]] > 1): print(0) return # Handling the case of # inequality elif (B[i % M] != arr[i]): print(0) return # Stores count of 0s # in B cnt = 0 # Traverse the array, B for i in range(0, M): # If B[i] is 0 if (B[i] == 0): # Update cnt cnt += 1 # Calculate factorial print(Fact(cnt))# Driver Codeif __name__ == '__main__': # Given M M = 4 # Given array arr = [ 1, 0, 3, 0, 0 ] # Size of the array N = len(arr) # Function Call numberOfWays(M, arr, N)# This code is contributed by shikhasingrajput |
C#
// C# program for the above approachusing System;class GFG{// Modular function// to calculate factorialstatic int Fact(int N){ // Stores factorial of N int result = 1; // Iterate over the range [1, N] for(int i = 1; i <= N; i++) { // Update result result = (result * i); } return result;}// Function to count ways to replace array// elements having 0s with non-zero elements// such that any M consecutive elements are distinctstatic void numberOfWays(int M, int[] arr, int N){ // Store m consecutive distinct elements // such that arr[i] is equal to B[i % M] int[] B = new int[M]; // Stores frequency of array elements int[] counter = new int[M + 1]; // Traverse the array arr[] for(int i = 0; i < N; i++) { // If arr[i] is non-zero if (arr[i] != 0) { // If B[i % M] is equal to 0 if (B[i % M] == 0) { // Update B[i % M] B[i % M] = arr[i]; // Update frequency of arr[i] counter[arr[i]]++; // If a duplicate element found // in M consecutive elements if (counter[arr[i]] > 1) { Console.WriteLine(0); return; } } // Handling the case of // inequality else if (B[i % M] != arr[i]) { Console.WriteLine(0); return; } } } // Stores count of 0s // in B[] int cnt = 0; // Traverse the array, B[] for(int i = 0; i < M; i++) { // If B[i] is 0 if (B[i] == 0) { // Update cnt cnt++; } } // Calculate factorial Console.WriteLine(Fact(cnt));}// Driver Codestatic public void Main(){ // Given M int M = 4; // Given array int[] arr = new int[]{ 1, 0, 3, 0, 0 }; // Size of the array int N = arr.Length; // Function Call numberOfWays(M, arr, N);}}// This code is contributed by Dharanendra L V |
Javascript
<script>// Javascript program of the above approach// Modular function// to calculate factorialfunction Fact(N){ // Stores factorial of N let result = 1; // Iterate over the range [1, N] for(let i = 1; i <= N; i++) { // Update result result = (result * i); } return result;} // Function to count ways to replace array// elements having 0s with non-zero elements// such that any M consecutive elements are distinctfunction numberOfWays(M, arr, N){ // Store m consecutive distinct elements // such that arr[i] is equal to B[i % M] let B = new Array(M).fill(0); // Stores frequency of array elements let counter = new Array(M+1).fill(0); // Traverse the array arr[] for(let i = 0; i < N; i++) { // If arr[i] is non-zero if (arr[i] != 0) { // If B[i % M] is equal to 0 if (B[i % M] == 0) { // Update B[i % M] B[i % M] = arr[i]; // Update frequency of arr[i] counter[arr[i]]++; // If a duplicate element found // in M consecutive elements if (counter[arr[i]] > 1) { document.write(0); return; } } // Handling the case of // inequality else if (B[i % M] != arr[i]) { document.write(0); return; } } } // Stores count of 0s // in B[] let cnt = 0; // Traverse the array, B[] for(let i = 0; i < M; i++) { // If B[i] is 0 if (B[i] == 0) { // Update cnt cnt++; } } // Calculate factorial document.write(Fact(cnt));} // Driver Code // Given M let M = 4; // Given array let arr = [ 1, 0, 3, 0, 0 ]; // Size of the array let N = arr.length; // Function Call numberOfWays(M, arr, N); </script> |
Output:
2
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!
