How is the minimum number of operations determined for this problem?

By summing the differences between each element and the target value for half the array, leveraging symmetry in the sequential odd numbers.

Why do we only need to consider half of the array?

The array is symmetric around the target; each operation on one side mirrors the other, so counting one half suffices.

What if n is very large, up to 104?

The formula approach still works in O(1) time and O(1) space, avoiding loops or simulation regardless of n.

Does the operation always involve subtracting 1 from one element and adding 1 to another?

Yes, each operation is exactly one unit transfer between any two indices to eventually equalize the array.

Is this a Math-driven solution pattern problem?

Exactly, recognizing the math-driven sequential odd-number pattern is key to efficiently computing minimum operations.

#1551

Medium

auto_awesome数学·driven

LeetCode 题解工作台

使数组中所有元素相等的最小操作数

存在一个长度为 n 的数组 arr ，其中 arr[i] = (2 * i) + 1 （ 0 ）。一次操作中，你可以选出两个下标，记作 x 和 y （ 0 ）并使 arr[x] 减去 1 、 arr[y] 加上 1 （即 arr[x] -=1 且 arr[y] += 1 ）。最终的目标是使数组中的…

数学

题目描述

存在一个长度为 n 的数组 arr ，其中 arr[i] = (2 * i) + 1 （ 0 <= i < n ）。

一次操作中，你可以选出两个下标，记作 x 和 y （ 0 <= x, y < n ）并使 arr[x] 减去 1 、arr[y] 加上 1 （即 arr[x] -=1 且 arr[y] += 1 ）。最终的目标是使数组中的所有元素都相等。题目测试用例将会保证：在执行若干步操作后，数组中的所有元素最终可以全部相等。

给你一个整数 n，即数组的长度。请你返回使数组 arr 中所有元素相等所需的 最小操作数 。

示例 1：

输入：n = 3
输出：2
解释：arr = [1, 3, 5]
第一次操作选出 x = 2 和 y = 0，使数组变为 [2, 3, 4]
第二次操作继续选出 x = 2 和 y = 0，数组将会变成 [3, 3, 3]

示例 2：

输入：n = 6
输出：9

提示：

1 <= n <= 10^4

lightbulb

解题思路

方法一：数学

根据题目描述，数组 $arr$ 是一个首项为 $1$ ，公差为 $2$ 的等差数列。那么数组前 $n$ 项的和为：

\begin{aligned} S_n &= \frac{n}{2} \times (a_1 + a_n) \\ &= \frac{n}{2} \times (1 + (2n - 1)) \\ &= n^2 \end{aligned}

由于一次操作中，一个数减一，另一个数加一，数组中所有元素的和不变。因此，数组中所有元素相等时，每个元素的值为 $S_n / n = n$ 。那么，数组中所有元素相等所需的最小操作数为：

\sum_{i=0}{\frac{n}{2}} (n - (2i + 1))

时间复杂度 $O(n)$ ，其中 $n$ 为数组长度。空间复杂度 $O(1)$ 。

1

2

3

4

class Solution:
    def minOperations(self, n: int) -> int:
        return sum(n - (i << 1 | 1) for i in range(n >> 1))

speed

复杂度分析

指标	值
时间	complexity is O(1) because a direct formula computes the sum of differences for half the array. Space complexity is O(1) since no extra array is stored; calculations are arithmetic based on n.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Expect you to notice the array's sequential odd-number pattern.
question_mark
Check if you compute target = sum(arr)/n before iterating.
question_mark
Look for symmetry to minimize operations, not brute force each pair.

warning

常见陷阱

外企场景

error
Trying to simulate each operation instead of using the sum formula.
error
Ignoring symmetry and overcounting operations for mirrored elements.
error
Miscomputing target as a middle element rather than the true average.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Arrays of even numbers instead of odd numbers but using the same operation rule.
arrow_right_alt
Allowing operations that adjust elements by more than 1 unit per move.
arrow_right_alt
Finding minimum operations when only adjacent elements can be adjusted.

help

常见问题

外企场景

继续练习

#1561 你可以获得的最大硬币数目 #1563 石子游戏 V #1569 将子数组重新排序得到同一个二叉搜索树的方案数