Last Updated: 22 Apr, 2021
Create Array
Easy
Asked in company
You are given an array “ARR”, with elements in strictly increasing order, and an integer ‘N’. You need to create the given “ARR” using numbers in the range [1, N].
You can create the given “ARR” using the following operations:
1. Add - Read the first element of the range and add it to the array.
2. Remove - Remove the last element added into the array.
3. Once, “ARR” is created, stop doing the operations.
Your task is to find all the operations in the sequential order that are needed to create the given “ARR”.
Input Format :
The first line contains a single integer ‘T’, denoting the number of test cases.
The first line of each test case contains two integers ‘M’ and ‘N’ denoting the number of elements in the given “ARR” and the integer denoting the upper limit of the range.
The next line of each test case contains ‘M’ space-separated integers denoting elements of “ARR”.
Output Format :
For each test case, print space-separated strings denoting operations required to create the given “ARR”.
Print the output of each test case in a separate line.
Note :
1. You don’t need to print anything. It has already been taken care of. Just implement the given function.
2. It is guaranteed that the answer is unique.
Constraints :
1 <= T <= 10
1 <= N <= 10^5
1 <= M <= 10^5
1 <= ARR[i] <= N
Where 'ARR[i]' is the element of the given array at index ‘i’.
Time limit: 1 sec
Approaches
The basic idea is that for every element, the first operation will always be the ‘Add’. If the element is not present in the ‘ARR’ array then we need to do a ‘Remove’ operation otherwise we will take the next element from the range.
Algorithm
- Initialize an array of string ‘operations’ to store all the operations performed.
- Take an integer ‘cur’ with the initial value ‘1’ denoting the current element that is taken from the range.
- Run a loop while ‘i’ is less than (size of ARR array - 1).
- Push “Add” to ‘operations’ as the first operation is always “Add”.
- If ARR[ i ] = cur, i.e. if the current element is present in the ‘ARR’ array, increment ‘i’ by ‘1’.
- Otherwise, push “Remove” to ‘operations’. It denotes that the current element is not present in the array.
- Increment ‘cur’ by ‘1’ to take the next element from the range.
- Return ‘operations’