How should I practice Maximum Number of Moves with Same Result?

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

Is Maximum Number of Moves with Same Result associated with Microsoft?

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

Problem · Array

Maximum Number of Moves with Same Result

Learn this problem

● MediumMicrosoftOA

See Microsoft hiring insights

Problem statement

You are given an array A consisting of N numbers. In one move you can delete either the first two, the last two, or the first and last elements of A. No move can be performed if the length of A is smaller than 2. The result of each move is the sum of the deleted elements.

Given an array A of N integers, returns the maximum number of moves that can be performed on A, such that all performed moves have the same result.

Warmest thanks to the ever-amazing spike!(๑ᵔ⤙ᵔ๑)

Function

maxNumMoves(A: int[]) → int

Examples

Example 1

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

The first move should delete two last elements (4 and 2 with sum = 6), then A = [3, 1, 5, 3, 3]. The second move may delete first and last elements (3 and 3 with sum = 6), then A = [1, 5, 3]. The third move should delete first two elements (1 and 5 with sum = 6), then A = [3].

Example 2

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

It is possible to delete the first and last elements four times, as each such pair of elements sums up to 6.

Example 3

A = [1, 9, 1, 1, 1, 1, 1, 1, 8, 1]return = 1

There is no way to perform move that results with the same sum more than once.

Example 4

A = [1, 9, 8, 9, 5, 1, 2]return = 3

The first move should delete the first two elements, then the second and third moves should delete first and last elements twice.

Example 5

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

One of the possible sequence of moves goes as follows: twice delete the last two elements, then delete the first and last elements, last move deletes the first two elements.

Constraints

N is an integer within the range [1..1,000];
each element of array A is an integer within the range [1..1,000,000,000].