Dado un entero positivo M y una array arr[] de tamaño N y faltan algunos enteros en la array representada como -1 , la tarea es encontrar el recuento de distintas arrays después de reemplazar todo -1 con los elementos sobre el rango [ 1, M] tal que la diferencia absoluta entre cualquier par de elementos adyacentes sea como máximo 1 .
Ejemplos:
Entrada: arr[] = {2, -1, 2}, M = 5
Salida: 3
Explicación:
Las arrays que siguen las condiciones dadas son {2, 1, 2}, {2, 2, 2} y {2, 3, 2}.Entrada: arr[] = {4, -1, 2, 1, -1, -1}, M = 10
Salida: 5
Enfoque: El problema dado se puede resolver usando Programación Dinámica basada en las siguientes observaciones:
- Considere una array 2D , digamos dp[][] donde dp[i][j] representa el recuento de arrays válidas de longitud i+1 que tienen su último elemento como j .
- Dado que la diferencia absoluta entre los elementos adyacentes debe ser como máximo 1 , para cualquier entero j , el entero adyacente válido puede ser j-1 , j y j+1 . Por lo tanto, cualquier estado dp[i][j] se puede calcular usando la siguiente relación:
dp[ i ][ j ] = dp[ i-1 ][ j ] + dp[ i-1 ][ j-1 ] + dp[ i-1 ][ j+1 ]
- En los casos en que arr[i] = -1 , calcule dp[i][j] = (dp[i-1][j] + dp[i-1][j-1] + dp[i-1][ j+1]) para todos los valores de j en el rango [1, M] .
- En los casos en que arr[i] != -1 , calcule dp[i][j] = (dp[i-1][j] + dp[i-1][j-1] + dp[i-1] [j+1]) para j = arr[i] .
- Tenga en cuenta que en los casos en que arr[0] = -1 , todos los valores en el rango [1, M] son accesibles como el primer elemento del arreglo, por lo tanto, inicialice dp[0][j] = 1 para todos los j en el rango [1 , M] de lo contrario, inicialice dp[0][arr[0]] = 1 .
- La respuesta requerida será la suma de todos los valores de dp[N – 1][j] para todos los j en el rango [1, M] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the count of possible
// arrays such that the absolute difference
// between any adjacent elements is atmost 1
int countArray(int arr[], int N, int M)
{
// Stores the dp states where dp[i][j]
// represents count of arrays of length
// i+1 having their last element as j
int dp[N][M + 2];
memset(dp, 0, sizeof dp);
// Case where 1st array element is missing
if (arr[0] == -1) {
// All integers in range [1, M]
// are reachable
for (int j = 1; j <= M; j++) {
dp[0][j] = 1;
}
}
else {
// Only reachable integer is arr[0]
dp[0][arr[0]] = 1;
}
// Iterate through all values of i
for (int i = 1; i < N; i++) {
// If arr[i] is not missing
if (arr[i] != -1) {
// Only valid value of j is arr[i]
int j = arr[i];
dp[i][j] += dp[i - 1][j - 1] + dp[i - 1][j]
+ dp[i - 1][j + 1];
}
// If arr[i] is missing
if (arr[i] == -1) {
// Iterate through all possible
// values of j in range [1, M]
for (int j = 1; j <= M; j++) {
dp[i][j] += dp[i - 1][j - 1] + dp[i - 1][j]
+ dp[i - 1][j + 1];
}
}
}
// Stores the count of valid arrays
int arrCount = 0;
// Calculate the total count of
// valid arrays
for (int j = 1; j <= M; j++) {
arrCount += dp[N - 1][j];
}
// Return answer
return arrCount;
}
// Driver Code
int main()
{
int arr[] = { 4, -1, 2, 1, -1, -1 };
int N = sizeof(arr) / sizeof(arr[0]);
int M = 10;
// Function Call
cout << countArray(arr, N, M);
return 0;
}
Java
// Java program of the above approach
class GFG
{
// Function to find the count of possible
// arrays such that the absolute difference
// between any adjacent elements is atmost 1
public static int countArray(int arr[], int N, int M)
{
// Stores the dp states where dp[i][j]
// represents count of arrays of length
// i+1 having their last element as j
int[][] dp = new int[N][M + 2];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M + 2; j++) {
dp[i][j] = 0;
}
}
// Case where 1st array element is missing
if (arr[0] == -1)
{
// All integers in range [1, M]
// are reachable
for (int j = 1; j <= M; j++) {
dp[0][j] = 1;
}
} else {
// Only reachable integer is arr[0]
dp[0][arr[0]] = 1;
}
// Iterate through all values of i
for (int i = 1; i < N; i++) {
// If arr[i] is not missing
if (arr[i] != -1) {
// Only valid value of j is arr[i]
int j = arr[i];
dp[i][j] += dp[i - 1][j - 1] + dp[i - 1][j] + dp[i - 1][j + 1];
}
// If arr[i] is missing
if (arr[i] == -1) {
// Iterate through all possible
// values of j in range [1, M]
for (int j = 1; j <= M; j++) {
dp[i][j] += dp[i - 1][j - 1] + dp[i - 1][j] + dp[i - 1][j + 1];
}
}
}
// Stores the count of valid arrays
int arrCount = 0;
// Calculate the total count of
// valid arrays
for (int j = 1; j <= M; j++) {
arrCount += dp[N - 1][j];
}
// Return answer
return arrCount;
}
// Driver Code
public static void main(String args[]) {
int arr[] = { 4, -1, 2, 1, -1, -1 };
int N = arr.length;
int M = 10;
// Function Call
System.out.println(countArray(arr, N, M));
}
}
// This code is contributed by _saurabh_jaiswal.
Python3
# Python 3 program of the above approach # Function to find the count of possible # arrays such that the absolute difference # between any adjacent elements is atmost 1 def countArray(arr, N, M): # Stores the dp states where dp[i][j] # represents count of arrays of length # i+1 having their last element as j dp = [[0 for i in range(M+2)] for j in range(N)] # Case where 1st array element is missing if (arr[0] == -1): # All integers in range [1, M] # are reachable for j in range(1,M+1,1): dp[0][j] = 1 else: # Only reachable integer is arr[0] dp[0][arr[0]] = 1 # Iterate through all values of i for i in range(1, N, 1): # If arr[i] is not missing if(arr[i] != -1): # Only valid value of j is arr[i] j = arr[i] dp[i][j] += dp[i - 1][j - 1] + dp[i - 1][j] + dp[i - 1][j + 1] # If arr[i] is missing if (arr[i] == -1): # Iterate through all possible # values of j in range [1, M] for j in range(1,M+1,1): dp[i][j] += dp[i - 1][j - 1] + dp[i - 1][j] + dp[i - 1][j + 1] # Stores the count of valid arrays arrCount = 0 # Calculate the total count of # valid arrays for j in range(1,M+1,1): arrCount += dp[N - 1][j] # Return answer return arrCount # Driver Code if __name__ == '__main__': arr = [4, -1, 2, 1, -1, -1] N = len(arr) M = 10 # Function Call print(countArray(arr, N, M)) # This code is contributed by SURENDRA_GANGWAR.
C#
// C# program of the above approach
using System;
public class GFG
{
// Function to find the count of possible
// arrays such that the absolute difference
// between any adjacent elements is atmost 1
public static int countArray(int []arr, int N, int M)
{
// Stores the dp states where dp[i][j]
// represents count of arrays of length
// i+1 having their last element as j
int[,] dp = new int[N, M + 2];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M + 2; j++) {
dp[i, j] = 0;
}
}
// Case where 1st array element is missing
if (arr[0] == -1)
{
// All integers in range [1, M]
// are reachable
for (int j = 1; j <= M; j++) {
dp[0, j] = 1;
}
} else {
// Only reachable integer is arr[0]
dp[0, arr[0]] = 1;
}
// Iterate through all values of i
for (int i = 1; i < N; i++) {
// If arr[i] is not missing
if (arr[i] != -1) {
// Only valid value of j is arr[i]
int j = arr[i];
dp[i, j] += dp[i - 1, j - 1] + dp[i - 1, j] + dp[i - 1, j + 1];
}
// If arr[i] is missing
if (arr[i] == -1) {
// Iterate through all possible
// values of j in range [1, M]
for (int j = 1; j <= M; j++) {
dp[i, j] += dp[i - 1, j - 1] + dp[i - 1, j] + dp[i - 1, j + 1];
}
}
}
// Stores the count of valid arrays
int arrCount = 0;
// Calculate the total count of
// valid arrays
for (int j = 1; j <= M; j++) {
arrCount += dp[N - 1, j];
}
// Return answer
return arrCount;
}
// Driver Code
public static void Main(String[] args) {
int []arr = { 4, -1, 2, 1, -1, -1 };
int N = arr.Length;
int M = 10;
// Function Call
Console.WriteLine(countArray(arr, N, M));
}
}
// This code is contributed by AnkThon.
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to find the count of possible
// arrays such that the absolute difference
// between any adjacent elements is atmost 1
function countArray(arr, N, M) {
// Stores the dp states where dp[i][j]
// represents count of arrays of length
// i+1 having their last element as j
let dp = new Array(N);
// Loop to create 2D array using 1D array
for (let i = 0; i < dp.length; i++) {
dp[i] = new Array(M + 2).fill(0);
}
// Case where 1st array element is missing
if (arr[0] == -1) {
// All integers in range [1, M]
// are reachable
for (let j = 1; j <= M; j++) {
dp[0][j] = 1;
}
}
else {
// Only reachable integer is arr[0]
dp[0][arr[0]] = 1;
}
// Iterate through all values of i
for (let i = 1; i < N; i++) {
// If arr[i] is not missing
if (arr[i] != -1) {
// Only valid value of j is arr[i]
let j = arr[i];
dp[i][j] += dp[i - 1][j - 1] + dp[i - 1][j]
+ dp[i - 1][j + 1];
}
// If arr[i] is missing
if (arr[i] == -1) {
// Iterate through all possible
// values of j in range [1, M]
for (let j = 1; j <= M; j++) {
dp[i][j] += dp[i - 1][j - 1] + dp[i - 1][j]
+ dp[i - 1][j + 1];
}
}
}
// Stores the count of valid arrays
let arrCount = 0;
// Calculate the total count of
// valid arrays
for (let j = 1; j <= M; j++) {
arrCount += dp[N - 1][j];
}
// Return answer
return arrCount;
}
// Driver Code
let arr = [4, -1, 2, 1, -1, -1];
let N = arr.length;
let M = 10;
// Function Call
document.write(countArray(arr, N, M));
// This code is contributed by Potta Lokesh
</script>
Producción:
5
Complejidad temporal: O(N*M)
Espacio auxiliar: O(N*M)
Publicación traducida automáticamente
Artículo escrito por ramandeep8421 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA