Dada una array arr[] que consta de N enteros en el rango [0, M] y un entero M , la tarea es contar el número de formas de reemplazar todos los elementos de la array cuyo valor es 0 con valores distintos de cero del rango [ 0, M] tales que todos los M elementos consecutivos posibles son distintos.
Ejemplos:
Entrada: arr[] = { 1, 0, 3, 0, 0 }, M = 4
Salida: 2
Explicación:
posibles formas de reemplazar arr[1], arr[3] y arr[4] con valores distintos de cero como que ningún M( = 4) elementos consecutivos contiene elementos duplicados son { { 1, 2, 3, 4, 1 }, { 1, 4, 3, 2, 1 } }.
Por lo tanto, la salida requerida es 2.Entrada: arr[] = {0, 1, 2, 1, 0}, M = 4
Salida: 0
Explicación: Tales arreglos no son posibles.
Enfoque: la idea es reemplazar 0 s con elementos distintos de cero, de modo que arr[i] debe ser igual a arr[i % M] . Siga los pasos a continuación para resolver el problema:
- Inicialice una array B[] de tamaño M + 1 para almacenar M elementos de array de array consecutivos de modo que arr[i] sea igual a B[i % M] .
- Atraviese la array y verifique las siguientes condiciones:
- Si arr[i] no es 0 y B[i % M] es 0 , entonces B[i % M] será igual a arr[i] ya que este número debe estar presente tal cual.
- Si arr[i] no es igual a B[i % M] , imprima 0 ya que no existen tales arreglos.
- Calcule la cuenta de 0 s en la array B[] , digamos X .
- Entonces, existen arreglos posibles del factorial X , por lo tanto, imprima el valor del factorial X.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Modular function
// to calculate factorial
long 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 distinct
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[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 Code
int 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 approach
import java.io.*;
class GFG{
// Modular function
// to calculate factorial
static 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 distinct
static 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 Code
public 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 factorial def 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 distinct def 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 Code if __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 approach
using System;
class GFG{
// Modular function
// to calculate factorial
static 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 distinct
static 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 Code
static 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 factorial
function 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 distinct
function 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>
Producción:
2
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por ujjwalgoel1103 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA