FastPrepFastPrep
Problem Brief

Minimum Number Of Moves to Obtain

FULLTIMEOA
See Google online assessment and hiring insights

Things begin with an array filled with N zeros, and, we, as a team, want to obtain an array A.

In one move, we can choose an arbitrary inverval and increase all the elements within that inverval by 1. For example:::

We can transform [0, 0, 0, 0, 0] into [0, 1, 1, 1, 0] in a single move.

BUT! We need three moves to obtain [1, 0, 1, 2, 2]. One possible sequence of moves is: [0, 0, 0, 0 , 0] -> [0, 0, 1, 1, 1] -> [0, 0, 1, 2, 2] -> [1, 0, 1, 2, 2], where -> denotes a single move.

What is the minimum number of moves needed to obtain A? Starting from a zero-filled array?

Given an array A of length N, returns an integer that represents the minimum number of moves needed to transform a zero-filled array into A

1Example 1

Input
A = [2, 1, 3]
Output
4
Explanation
The following sequence of moves leads to the solution - [0, 0, 0] → [1, 1, 1] → [2, 1, 1] → [2, 1, 2] → [2, 1, 3]

2Example 2

Input
A = [2, 2, 0, 0, 1]
Output
3
Explanation
The following sequence of moves leads to the solution: [0, 0, 0, 0, 0] → [1, 1, 0, 0, 0] → [2, 2, 0, 0, 0] → [2, 2, 0, 0, 1].

3Example 3

Input
A = [5, 4, 2, 4, 1]
Output
7
Explanation
One possible optimal sequence ‍‌‌‍‌‍‍‍‍‌‌‌‍‌‍‍‌‍‌of moves is: [0, 0, 0, 0, 0] → [1, 1, 1, 1, 1] → [2, 2, 2, 2, 1] → [3, 3, 2, 2, 1] → [4, 4, 2, 2, 1] → [5, 4, 2, 2, 1] → [5, 4, 2, 3, 1] → [5, 4, 2, 4, 1].

Constraints

Limits and guarantees your solution can rely on.

  • N is an integer within the range [1..100,000]
  • each element of array A is an integer within the range [0..1,000,000,000]
  • we guarantee that the answer will not exceed 1,000,000,000
    • public int googleMinimumNumberOfMovesToObtain(int[] arr) {
  // Write your code here :)
}
    Input

    A

    [2, 1, 3]

    Output

    4

    Sign in to submit your solution.