Construct Array by doing B[i] = B[i – 1] + 1
Given an array A[] of size N. You have to take another array B of size N and fill it with all 0’s. Find the minimum operations required to make array A[] from B[] where you can change a value of B[i] = B[i – 1] + 1. If it is not possible to make a return -1
Input:- N = 5, A = {0, 0, 1, 2, 0}
Output: 2
Explanation: Initial array B is {0, 0, 0, 0, 0}
- After one operation we will change B[2] = B[1] + 1, and B will become {0, 0, 1, 0, 0}
- After second operation we will change B[3] = B[2] + 1, and B will become {0, 0, 1, 2, 0}
Input: N = 3, A = {1, 0, 1}
Output: -1
Explanation: As the first element of A is 1 and there is no element at A[0-1], we can not change the first element of the array from 0 to any number.
Approach: This can be solved with the following idea:
We will start traversing the array from backward that is from N – 1, because we have to check if the element is equal to A[i – 1] + 1 or not, and based on that we have to do operations.
Steps involved in the implementation of code:
- If A[i] == A[i-1] + 1 then only one operation is needed to make this element form A[i – 1]’th element.
- If A[i] == A[i-1] then the A[i] operation is needed to make the current element let me explain this with an example in the below steps
- Take array {0, 1, 2, 0} in this there is no element like A[i] == A[i – 1] and operation need is {0, 0, 0, 0} -> {0, 1, 0, 0} -> {0, 1, 2, 0}. So 2 operations are needed.
- Now just modify the array to {0, 1, 2, 2} now the operation required will be 4 that is we have to do 2 more operations as compared to the previous example just because we have added A[3] = 2. So, the operation will be as follows {0, 0, 0, 0} -> {0, 0, 1, 0} -> {0, 0, 1, 2} -> {0, 1, 1, 2} -> {0, 1, 2, 2}. So 4 operation is required
- If we got 1 at A[i] then do not care about A[i-1], just add 1 operation to your answer like {0, 1, 2, 1}, then the operation will be like {0, 0, 0, 0} -> {0, 1, 0, 0} -> {0, 1, 0, 1} -> {0, 1, 2, 1}.
- If we do not get any relation as in the previous step then return -1.
Below is the implementation of the code:
C++
|
Time Complexity: O(N)
Auxiliary Space: O(1)
Given an array A[] of size N. You have to take another array B of size N and fill it with all 0’s. Find the minimum operations required to make array A[] from B[] where you can change a value of B[i] = B[i – 1] + 1. If it is not possible to make a return -1
Input:- N = 5, A = {0, 0, 1, 2, 0}
Output: 2
Explanation: Initial array B is {0, 0, 0, 0, 0}
- After one operation we will change B[2] = B[1] + 1, and B will become {0, 0, 1, 0, 0}
- After second operation we will change B[3] = B[2] + 1, and B will become {0, 0, 1, 2, 0}
Input: N = 3, A = {1, 0, 1}
Output: -1
Explanation: As the first element of A is 1 and there is no element at A[0-1], we can not change the first element of the array from 0 to any number.
Approach: This can be solved with the following idea:
We will start traversing the array from backward that is from N – 1, because we have to check if the element is equal to A[i – 1] + 1 or not, and based on that we have to do operations.
Steps involved in the implementation of code:
- If A[i] == A[i-1] + 1 then only one operation is needed to make this element form A[i – 1]’th element.
- If A[i] == A[i-1] then the A[i] operation is needed to make the current element let me explain this with an example in the below steps
- Take array {0, 1, 2, 0} in this there is no element like A[i] == A[i – 1] and operation need is {0, 0, 0, 0} -> {0, 1, 0, 0} -> {0, 1, 2, 0}. So 2 operations are needed.
- Now just modify the array to {0, 1, 2, 2} now the operation required will be 4 that is we have to do 2 more operations as compared to the previous example just because we have added A[3] = 2. So, the operation will be as follows {0, 0, 0, 0} -> {0, 0, 1, 0} -> {0, 0, 1, 2} -> {0, 1, 1, 2} -> {0, 1, 2, 2}. So 4 operation is required
- If we got 1 at A[i] then do not care about A[i-1], just add 1 operation to your answer like {0, 1, 2, 1}, then the operation will be like {0, 0, 0, 0} -> {0, 1, 0, 0} -> {0, 1, 0, 1} -> {0, 1, 2, 1}.
- If we do not get any relation as in the previous step then return -1.
Below is the implementation of the code:
C++
|
Time Complexity: O(N)
Auxiliary Space: O(1)