Given two arrays, arr1[] of length N1 and arr2[] of length N2, consisting of numbers from 1 to 9 and arr1[] has some missing entries denoted by 0, the task is to replace the missing entries of arr1[] with elements in range [1, 9] such that arr2[] is not a subsequence of the new array arr1[].
Examples:
Input: arr1[] = {2, 1, 0, 3}, N1 = 4, arr2[] = {1, 2}, N2 = 2
Output: {2, 1, 1, 3}
Explanation: Here arr1[2] = 0. So replace arr1[2] with 1.
So arr2[] is not a subsequence of the newly formed arr1[].Input: arr1[] = {2, 2, 0, 3, 0, 4}, N1 = 6, arr2 = {2, 3}, N2 = 2
Output: IMPOSSIBLE
Explanation: It is not possible to form such an array that does not have
arr2[] as a subsequence. because arr1[] already has arr2[] as a subsequence.
Approach: The approach to the problem is based on the two possibilities given below:
- arr2 is already a subsequence of arr1 (when not considering the missing elements).
- arr2 is not already a subsequence of arr1 (when not considering the missing elements).
If arr2[] is not already a subsequence, try to fill all the empty elements of arr1[] with each of the entry from [1, 9] and check if the formed array has all the elements of arr2[] in order to check for arr2[] being a subsequence of the arr1[].
Follow the steps mentioned below to implement the idea.
- Iterate through all the possible elements in [1, 9], and store this in i.
- Construct an empty array, of size N1.
- Initialize a variable (say index = 0) to track how many elements of arr2 have appeared so far in the resultant array.
- Iterate through all elements of arr1[].
- If a missing element is encountered, place i at the corresponding index of the resultant array.
- Otherwise, just place the same element as in arr1[].
- If this element is equal to arr2[index] (i.e. the first element from arr2 that has not appeared in the resultant array), increment index by 1.
- After iterating through the elements of arr1, if index is not equal to N2, that means all elements of arr2 did not appear in resultant array.
- Return it as the final array.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// function to form the resultant arrayvector<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 Codeint 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
# Python3 code to implement the approach# function to form the resultant arraydef 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 Codeif __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#
// C# code to implement the approachusing 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. |
Javascript
<script>// JavaScript code to implement the approach// function to form the resultant arrayfunction 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 Codelet arr1 = [2, 1, 0, 3]let N1 = 4let arr2 = [1, 2]let N2 = 2 // Function Callans = formArr(arr1, N1, arr2, N2)if(ans) document.write(ans)else document.write("IMPOSSIBLE")// This code is contributed by shinjanpatra</script> |
Java
// Java code for above approachimport java.io.*;import java.util.*;class GFG {// function to form the resultant arraypublic 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"); } }} |
Output
[2, 1, 1, 3]
Time Complexity: O(N1)
Auxiliary Space: O(N1)
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!
