Horje
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++

// C++ implementation of code
#include <bits/stdc++.h>
using namespace std;
 
// Function to get minimum operations
int minOperation(int N, vector<int>& A)
{
 
    // We can not change first element
    // from 0 to any other number
    if (A[0] != 0)
        return -1;
 
    // Variable to store answer
    int ans = 0;
 
    // Iterating over arry
    for (int i = N - 1; i > 0; i--) {
 
        // If element is next greater
        // than previous
        if (A[i] == A[i - 1] + 1)
            ans++;
 
        // If element is 1
        else if (A[i] == 1)
            ans++;
 
        // If elements are equal
        else if (A[i] == A[i - 1])
            ans += A[i];
 
        else
            return -1;
    }
    return ans;
}
 
// Driver code
int main()
{
 
    int N = 4;
 
    vector<int> A = { 0, 1, 2, 2 };
 
    // Function call
    cout << minOperation(N, A) << endl;
 
    return 0;
}

Java

import java.util.*;
 
public class Main {
     
    // Function to get minimum operations
    public static int minOperation(int N, ArrayList<Integer> A) {
 
        // We can not change first element
        // from 0 to any other number
        if (A.get(0) != 0)
            return -1;
 
        // Variable to store answer
        int ans = 0;
 
        // Iterating over array
        for (int i = N - 1; i > 0; i--) {
 
            // If element is next greater
            // than previous
            if (A.get(i) == A.get(i - 1) + 1)
                ans++;
 
            // If element is 1
            else if (A.get(i) == 1)
                ans++;
 
            // If elements are equal
            else if (A.get(i) == A.get(i - 1))
                ans += A.get(i);
 
            else
                return -1;
        }
        return ans;
    }
     
    // Driver code
    public static void main(String[] args) {
         
        int N = 4;
 
        ArrayList<Integer> A = new ArrayList<Integer>(Arrays.asList(0, 1, 2, 2));
 
        // Function call
        System.out.println(minOperation(N, A));
    }
}
 
// This code is contributed by Prajwal Kandekar

Python3

# Function to get minimum operations
def minOperation(N, A):
    # We can not change first element
    # from 0 to any other number
    if A[0] != 0:
        return -1
 
    # Variable to store answer
    ans = 0
 
    # Iterating over array
    for i in range(N - 1, 0, -1):
        # If element is next greater
        # than previous
        if A[i] == A[i - 1] + 1:
            ans += 1
        # If element is 1
        elif A[i] == 1:
            ans += 1
        # If elements are equal
        elif A[i] == A[i - 1]:
            ans += A[i]
        else:
            return -1
    return ans
 
# Driver code
if __name__ == "__main__":
    N = 4
    A = [0, 1, 2, 2]
    # Function call
    print(minOperation(N, A))

C#

// C# implementation of code
 
using System;
using System.Collections.Generic;
 
public class GFG
{
 
  // Function to get minimum operations
  public static int MinOperation(int N, List<int> A)
  {
     
    // We can not change first element
    // from 0 to any other number
    if (A[0] != 0) {
      return -1;
    }
 
    // Variable to store answer
    int ans = 0;
 
    // Iterating over array
    for (int i = N - 1; i > 0; i--)
    {
       
      // If element is next greater
      // than previous
      if (A[i] == A[i - 1] + 1) {
        ans++;
      }
       
      // If element is 1
      else if (A[i] == 1) {
        ans++;
      }
      // If elements are equal
      else if (A[i] == A[i - 1]) {
        ans += A[i];
      }
      else {
        return -1;
      }
    }
    return ans;
  }
 
  // Driver code
  public static void Main()
  {
    int N = 4;
    List<int> A = new List<int>{ 0, 1, 2, 2 };
 
    // Function call
    Console.WriteLine(MinOperation(N, A));
  }
}

Javascript

// Javascript implementation of code
 
// Function to get minimum operations
function minOperation(N, A) {
  // We can not change first element
  // from 0 to any other number
  if (A[0] !== 0) {
    return -1
  }
 
  // Variable to store answer
  let ans = 0
 
  // Iterating over array
  for (let i = N - 1; i > 0; i--) {
    // If element is next greater
    // than previous
    if (A[i] === A[i - 1] + 1) {
      ans += 1
    // If element is 1
    } else if (A[i] === 1) {
      ans += 1
    // If elements are equal
    } else if (A[i] === A[i - 1]) {
      ans += A[i]
    } else {
      return -1
    }
  }
  return ans
}
 
// Driver code
 
  const N = 4
  const A = [0, 1, 2, 2]
  // Function call
  console.log(minOperation(N, A))

Output

4

Time Complexity: O(N)
Auxiliary Space: O(1)


 


Reffered: https://www.geeksforgeeks.org

DSA

Related
Introduction to Block Sort Introduction to Block Sort
Introduction to Smooth Sort Introduction to Smooth Sort
Find anagrams in linked list Find anagrams in linked list
Hashing meaning in DSA Hashing meaning in DSA
Indegree of a Graph Indegree of a Graph

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 12



 

Horje