Reemplace los espacios vacíos con números [1, 9] de modo que otra array no sea una subsecuencia

Dadas dos arrays, arr1[] de longitud N1 y arr2[] de longitud N2 , que consisten en números del 1 al 9 y arr1[] tiene algunas entradas faltantes indicadas por 0, la tarea es reemplazar las entradas faltantes de arr1[] con elementos en el rango [1, 9] tales que arr2[] no es una subsecuencia de la nueva array arr1[] .

Ejemplos:

Entrada: arr1[] = {2, 1, 0, 3}, N1 = 4, arr2[] = {1, 2}, N2 = 2
Salida: {2, 1, 1, 3}
Explicación: Aquí arr1[2 ] = 0. Entonces reemplace arr1[2] con 1. 
Entonces arr2[] no es una subsecuencia del arr1[] recién formado.

Entrada: arr1[] = {2, 2, 0, 3, 0, 4}, N1 = 6, arr2 = {2, 3}, N2 = 2
Salida: IMPOSIBLE  Explicación: No es posible formar una array tal que no tiene arr2[] como subsecuencia. porque arr1[] ya tiene arr2[] como subsecuencia. 

Enfoque: El enfoque del problema se basa en las dos posibilidades que se presentan a continuación:

1. arr2 ya es una subsecuencia de arr1 (sin considerar los elementos que faltan).
2. arr2 no es ya una subsecuencia de arr1 (cuando no se consideran los elementos que faltan).

Si arr2[] aún no es una subsecuencia, intente llenar todos los elementos vacíos de arr1[] con cada una de las entradas de [1, 9] y verifique si la array formada tiene todos los elementos de arr2[] para verificar siendo arr2[] una subsecuencia de arr1[].

Siga los pasos mencionados a continuación para implementar la idea.

• Iterar a través de todos los elementos posibles en [1, 9] y almacenar esto en i .
  • Construya una array vacía, de tamaño N1 .
  • Inicialice una variable (digamos index = 0) para rastrear cuántos elementos de arr2 han aparecido hasta ahora en la array resultante. 
  • Iterar a través de todos los elementos de arr1[] . 
    • Si se encuentra un elemento faltante, coloque i en el índice correspondiente de la array resultante.
    • De lo contrario, simplemente coloque el mismo elemento que en arr1[] . 
    • Si este elementoes igual a arr2[índice] (es decir, el primer elemento de arr2 que no ha aparecido en la array resultante), incrementa el índice en 1.
  • Después de iterar a través de los elementos de arr1 , si el índice no es igual a N2 , eso significa que todos los elementos de arr2 no aparecieron en la array resultante.
  • Devuélvelo como la array final.

A continuación se muestra la implementación del enfoque anterior:

// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
 
// function to form the resultant array
vector<int> formArr(vector<int>& arr1, int N1,
                    vector<int>& arr2, int N2)
{
    // Iterating through all the possible
    // values
    for (int i = 1; i < 10; i++) {
        // Tracks how many elements of arr2
        // have appeared so far
        // in resultant array, arr3[]
        int index = 0;
 
        // Initializing resultant array
        vector<int> arr3(N1, INT_MAX);
 
        // Iterating through elements of arr1
        for (int j = 0; j < N1; j++) {
 
            // If element is not missing,
            // just copy it to arr3
            if (arr1[j])
                arr3[j] = arr1[j];
 
            // Else, copy i to arr3
            else
                arr3[j] = i;
 
            // If arr2[index] == arr3[j], then
            // another element of arr2 has
            // appeared in the final array,
            // and increase index counter by 1
            if (N2 > index && arr2[index] == arr3[j])
                index += 1;
        }
 
        // If index != N2, then that means
        // all elements of A2 did not appear
        // in Arr. Therefore, it is NOT a
        // subsequence
        if (index != N2)
            return arr3;
    }
 
    return {};
}
 
// Driver Code
int main()
{
    vector<int> arr1 = { 2, 1, 0, 3 };
    int N1 = 4;
    vector<int> arr2 = { 1, 2 };
    int N2 = 2;
 
    // Function Call
    vector<int> ans = formArr(arr1, N1, arr2, N2);
    if (ans.size() > 0) {
        for (int i : ans) {
            cout << i << " ";
        }
    }
    else {
 
        cout << "IMPOSSIBLE";
    }
    return 0;
}
 
// This code is contributed by Rohit Pradhan

# Python3 code to implement the approach
 
# function to form the resultant array
def formArr(arr1, N1, arr2, N2):
    # Iterating through all the possible
    # values
    for i in range(1, 10):
        # Tracks how many elements of arr2
        # have appeared so far
        # in resultant array, arr3[]
        index = 0
         
        # Initializing resultant array
        arr3 = [None] * N1
         
        # Iterating through elements of arr1
        for j in range(N1):
             
            # If element is not missing,
            # just copy it to arr3
            if arr1[j]:
                arr3[j] = arr1[j]
             
            # Else, copy i to arr3
            else:
                arr3[j] = i
                 
            # If arr2[index] == arr3[j], then
            # another element of arr2 has
            # appeared in the final array,
            # and increase index counter by 1
            if N2 > index and arr2[index] == arr3[j]:
                index += 1
         
        # If index != N2, then that means
        # all elements of A2 did not appear
        # in Arr. Therefore, it is NOT a
        # subsequence
        if index != N2:
            return arr3
    return []
 
# Driver Code
if __name__ == '__main__':
    arr1 = [2, 1, 0, 3]
    N1 = 4
    arr2 = [1, 2]
    N2 = 2
     
    # Function Call
    ans = formArr(arr1, N1, arr2, N2)
    if ans:
        print(ans)
    else:
        print("IMPOSSIBLE")

// C# code to implement the approach
using System;
 
class GFG
{
 
  // function to form the resultant array
  static int[] formArr(int[] arr1, int N1, int[] arr2,
                       int N2)
  {
 
    // Iterating through all the possible
    // values
    for (int i = 1; i < 10; i++) {
      // Tracks how many elements of arr2
      // have appeared so far
      // in resultant array, arr3[]
      int index = 0;
 
      // Initializing resultant array
      int[] arr3 = new int[N1];
      for (int x = 0; x < N1; x++) {
        arr3[x] = Int32.MaxValue;
      }
 
      // Iterating through elements of arr1
      for (int j = 0; j < N1; j++) {
 
        // If element is not missing,
        // just copy it to arr3
        if (arr1[j] != 0)
          arr3[j] = arr1[j];
 
        // Else, copy i to arr3
        else
          arr3[j] = i;
 
        // If arr2[index] == arr3[j], then
        // another element of arr2 has
        // appeared in the final array,
        // and increase index counter by 1
        if (N2 > index && arr2[index] == arr3[j])
          index += 1;
      }
 
      // If index != N2, then that means
      // all elements of A2 did not appear
      // in Arr. Therefore, it is NOT a
      // subsequence
      if (index != N2)
        return arr3;
    }
    int[] empty = {};
    return empty;
  }
 
  // Driver Code
  public static void Main()
  {
    int[] arr1 = { 2, 1, 0, 3 };
    int N1 = 4;
    int[] arr2 = { 1, 2 };
    int N2 = 2;
 
    // Function Call
    int[] ans = formArr(arr1, N1, arr2, N2);
    if (ans.Length > 0) {
      for (int i = 0; i < ans.Length; i++) {
        Console.Write(ans[i] + " ");
      }
    }
    else {
 
      Console.Write("IMPOSSIBLE");
    }
  }
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
 
// JavaScript code to implement the approach
 
// function to form the resultant array
function formArr(arr1, N1, arr2, N2)
{
 
    // Iterating through all the possible
    // values
    for(let i = 1; i < 10; i++)
    {
     
        // Tracks how many elements of arr2
        // have appeared so far
        // in resultant array, arr3[]
        let index = 0
         
        // Initializing resultant array
        let arr3 = new Array(N1).fill(null)
         
        // Iterating through elements of arr1
        for(let j=0;j<N1;j++){
             
            // If element is not missing,
            // just copy it to arr3
            if(arr1[j])
                arr3[j] = arr1[j]
             
            // Else, copy i to arr3
            else
                arr3[j] = i
                 
            // If arr2[index] == arr3[j], then
            // another element of arr2 has
            // appeared in the final array,
            // and increase index counter by 1
            if(N2 > index && arr2[index] == arr3[j])
                index += 1
        }
         
        // If index != N2, then that means
        // all elements of A2 did not appear
        // in Arr. Therefore, it is NOT a
        // subsequence
        if(index != N2)
            return arr3
    }
    return []
}
 
// Driver Code
 
let arr1 = [2, 1, 0, 3]
let N1 = 4
let arr2 = [1, 2]
let N2 = 2
     
// Function Call
ans = formArr(arr1, N1, arr2, N2)
if(ans)
    document.write(ans)
else
    document.write("IMPOSSIBLE")
 
// This code is contributed by shinjanpatra
 
</script>

// Java code for above approach
import java.io.*;
import java.util.*;
 
class GFG {
 
// function to form the resultant array
public static int[] formArr(int[] arr1, int N1, int[] arr2,
                    int N2)
{
 
    // Iterating through all the possible
    // values
    for (int i = 1; i < 10; i++) {
    // Tracks how many elements of arr2
    // have appeared so far
    // in resultant array, arr3[]
    int index = 0;
 
    // Initializing resultant array
    int[] arr3 = new int[N1];
    for (int x = 0; x < N1; x++) {
        arr3[x] = Integer.MAX_VALUE;
    }
 
    // Iterating through elements of arr1
    for (int j = 0; j < N1; j++) {
 
        // If element is not missing,
        // just copy it to arr3
        if (arr1[j] != 0)
        arr3[j] = arr1[j];
 
        // Else, copy i to arr3
        else
        arr3[j] = i;
 
        // If arr2[index] == arr3[j], then
        // another element of arr2 has
        // appeared in the final array,
        // and increase index counter by 1
        if (N2 > index && arr2[index] == arr3[j])
        index += 1;
    }
 
    // If index != N2, then that means
    // all elements of A2 did not appear
    // in Arr. Therefore, it is NOT a
    // subsequence
    if (index != N2)
        return arr3;
    }
    int[] empty = {};
    return empty;
}
 
 
  // Driver Code
  public static void main(String[] args)
  {
     int[] arr1 = { 2, 1, 0, 3 };
    int N1 = 4;
    int[] arr2 = { 1, 2 };
    int N2 = 2;
 
    // Function Call
    int[] ans = formArr(arr1, N1, arr2, N2);
    if (ans.length > 0) {
    for (int i = 0; i < ans.length; i++) {
        System.out.print(ans[i] + " ");
    }
    }
    else {
 
    System.out.print("IMPOSSIBLE");
    }
  }
}

[2, 1, 1, 3]

Complejidad temporal: O(N1)
Espacio auxiliar: O(N1)