Logic to determine if target array is reachable by incrementing all but one index each operation

1 week ago 4
ARTICLE AD BOX

I’m solving a competitive programming problem and I’m stuck on the logic behind it.

Problem

You are given an array A of length N. You start with another array B of the same length, initialized with all zeros.

Allowed Operation

In one operation:

Choose (N−1) distinct indices and add +1 to each of them (meaning exactly one index is skipped in every operation)

Goal

Determine whether it is possible to transform B into A using any number of operations. If it is possible, return the minimum number of operations. Otherwise, return -1.

Example Input / Output Input: 2 3 3 1 0 2 0 2

Output: -1 2

Expected behavior

For A = [0, 2], we can skip the same index twice → answer is 2.

For A = [3, 1, 0], it seems impossible → answer should be -1.

What I have tried

I observed that each operation increases the sum of the array by (N−1)

So I suspect that sum(A) must be divisible by (N−1)

I am not sure how to handle the relationship with the maximum element, or how to prove correctness

Actual problem

I’m unsure how to determine exactly when the transformation is possible or impossible, and how to compute the minimum operations.

Question

What is the correct logic or mathematical condition needed to determine whether A can be formed and to compute the minimum number of operations? (Not looking for full code, just explanation.)

Read Entire Article