FastPrepGet Minimum Operations

Get Minimum Operations

Rubrik logoRubrik● MediumINTERNOA
Learn

Problem statement

Given two arrays change and arr that consist of n and m integers respectively.

In the ith operation, one of the two operations can be performed:

  • you can choose to decrement any element of arr by 1 or do nothing.
  • if change[i] > 0 and arr[change[i]] = 0, it can be changed to NULL.

Assume indexing starts from 1, find the minimum number of operations required to change all the elements of the array to NULL or report -1 if it is not possible.

Function

getMinOperations(change: int[], arr: int[]) → int

Complete the function getMinOperations in the editor below.

getMinOperations has the following parameter(s):

  1. int change[n]: an array of integers
  2. int arr[m]: an array of integers

Returns int: the minimum number of operations required to change all the elements to NULL, or -1 if it is not possible

Examples

Example 1

change = [0, 1, 0, 2]arr = [1, 1]return = 4

Consider n = 4 and m = 2 change[] = [0, 1, 0, 2], arr[] = [1, 1]

  • In the first operation, arr[1] can be decremented. The array becomes [0, 1].
  • In the second operation, since change[2] = 1 and arr[1] = 0, the first element can be changed to NULL. The array becomes [NULL, 1].
  • In the third operation, arr[2] can be decremented. The array becomes [NULL, 0].
  • In the fourth operation, since change[4] = 2 and arr[2] = 0, the second element can be changed to NULL. The array becomes [NULL, NULL].

This is one optimal path. Return the number of operations, 4.

Constraints

  • :o

More Rubrik problems

See Rubrik hiring insights
public int getMinOperations(int[] change, int[] arr) {
  // write your code here
}
change[0, 1, 0, 2]
arr[1, 1]
expected4
Checking account…