Problem Brief

Ensure Non-Zero Load Sum

See Amazon online assessment and hiring insights

Amazon SQS is a completely operated platform in the AWS ecosystem that enables dispatchers to submit and receivers to collect messages. Each message present in the sequence is symbolized by an integer, where a positive number indicates a submission by a dispatcher and a negative number denotes a retrieval by a receiver. The behavior of the queue is controlled by the "processing burden," calculated as the cumulative sum of message values over any consecutive group of messages.

To guarantee the queue's consistent operation, it is essential that the processing burden for any contiguous block of messages is never zero. A processing burden of zero would signify that the queue has lost its functional purpose, which is an undesirable sadness... :(

As a sharp software engineer with a total compensation of 💰 1.5M USD💸, your objective is to compute the least number of additional messages that must be injected into the sequence. Each added message may carry any integer value. The intention is to ensure that once these are inserted, no segment within the sequence yields a total processing burden of zero.

Given the array queueMessages, determine the minimal count of insertions necessary to fulfill this requirement.

1Example 1

Input

queueMessages = [1, -5, 3, 2, -5]

Output

Explanation

The SQS Queue contains a continuous segment [2, 4] that results in a processing burden of 0. One potential approach to adjust the provided array queueMessages is by placing a message carrying the value 100 after the third position. The revised array turns into [1, -5, 3, 100, 2, -5]. At this point, no consecutive segment within the array sums up to zero. Therefore, the least number of messages required to be inserted is 1.

Draft autosaves locally

public int minInsertionsToEnsureNonZeroLoadSum(int[] queueMessages) {
  // write your code here
}

Input

queueMessages

[1, -5, 3, 2, -5]

Output