How should I practice Minimum Number Of Moves to Obtain?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Google online assessment problems in FastPrep.

Is Minimum Number Of Moves to Obtain associated with Google?

FastPrep tags this as a Google coding interview or online assessment practice problem when the problem catalog has that company context.

Problem · Array

Minimum Number Of Moves to Obtain

Learn this problem

● EasyGoogleFULLTIMEOA

See Google hiring insights

Problem statement

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

Function

googleMinimumNumberOfMovesToObtain(A: int[]) → int

Examples

Example 1

A = [2, 1, 3]return = 4

The following sequence of moves leads to the solution - [0, 0, 0] → [1, 1, 1] → [2, 1, 1] → [2, 1, 2] → [2, 1, 3]

Example 2

A = [2, 2, 0, 0, 1]return = 3

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].

Example 3

A = [5, 4, 2, 4, 1]return = 7

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

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