We can check if the array is already balanced by storing 4 arrays, prefix minimum, prefix maximum, suffix minimum and suffix maximum. We will go to all indices $i(1 \leq i < N)$ and check if $F(B)$ equals $F(C)$ using our pre-computed arrays. If the array is already Balanced, the answer is 0.

Otherwise, we can always do 1 operation to make the array Balanced. Let us pick $i~=~2$, so we get $B = \{A_1, A_2\}$ and $C = \{A_3, A_4,..,A_N\}$. We can select $j = 2$ and set the value of $A_2$ to $A_1+F(C)$ and then $F(B)$ will equal $F(C)$.

Author’s solution: https://ideone.com/UqT1Cw

71%
Solution Ratio

serotoninEarliest,

Sumaya_1703110Fastest, 0.0s

serotoninLightest, 4.2 MB

serotoninShortest, 632B

Toph uses cookies. By continuing you agree to our Cookie Policy.