FastPrep
Problem · Array

Array Nullification

Learn this problem
● MediumQube Research & TechnologiesNEW GRADOA

Problem statement

You are given two arrays, change and arr, of lengths n and m, respectively. In each operation i, you can perform one of the following:

  1. You can decrement any element of arr by 1.
  2. If change[i] > 0 and arr[change[i]] = 0, you can change that element to NULL.

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

Function

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

Complete the function getMinOperations in the editor with the following parameters:

  • int change[n]: an array of integers
  • 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

Operations sequence:

  1. Decrement arr[1]: [0, 1]
  2. Change arr[1] to NULL since change[2] = 1 and arr[1] = 0: [NULL, 1]
  3. Decrement arr[2]: [NULL, 0]
  4. Change arr[2] to NULL since change[4] = 2 and arr[2] = 0: [NULL, NULL]

The answer is 4.

Constraints

  • 1 <= n <= 10^5

More Qube Research & Technologies problems

drafts saved locally
public int getMinOperations(int[] change, int[] arr) {
  // write your code here
}
change[0, 1, 0, 2]
arr[1, 1]
expected4
checking account