Create Array

Easy
0/40
Average time to solve is 15m
profile
Contributed by
6 upvotes
Asked in company
Deutsche Bank

Problem statement

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”.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1 :

2
3 4
1 2 4
2 3
1 2

Sample Output 1 :

Add Add Add Remove Add
Add Add

Explanation Of Sample Input 1 :

Test Case 1: 
In the given case N = 4, so the range is {1, 2, 3, 4}
Take 1 from the range and add it to the array. Array = [1].
Take 2 from the range and add it to the array, Array = [1, 2]
Take 3 from the range and add it to the array, Array = [1, 2, 3]
‘3’ is not required in the “ARR” so remove the last element i.e. ‘3’. Array = [1, 2]
Take 4 from the range and add it to the array, Array = [1, 2, 4].

Test Case 2: We have range = {1,2,3}.
Take 1 from the range and add it to the array, Array = [1].
Take 2 from the range and add it to the array, Array = [1, 2].
As the “ARR” array is created, stop reading elements from the range.

Sample Input 2 :

2
4 6
2 3 4 5 
1 1
1

Sample Output 2 :

Add Remove Add Add Add Add
Add
Hint

Try to check every member of the given range.

Approaches (1)
Brute Force

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’
Time Complexity

O(N), where ‘N’ is the number of members in the given range.

 

We are checking every element of the range until all the elements of the ‘ARR’  array are found. The maximum number in the ‘ARR’ array can be ‘N’. Therefore time complexity is O(N).

Space Complexity

O(N), where ‘N’ is the number of members in the given range.

 

We are using an array of strings to store the operations performed and the maximum number of operations can be ‘(2*N) - 1’. Therefore space complexity is O(N).

Code Solution
(100% EXP penalty)
Create Array
Full screen
Console