2485-找出中枢整数

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:15:46 2023-09-13 16:15:46 Updated    

给你一个正整数 n ，找出满足下述条件的 中枢整数 x ：

  • 1 和 x 之间的所有元素之和等于 x 和 n 之间所有元素之和。

返回中枢整数 __x 。如果不存在中枢整数，则返回 -1 。题目保证对于给定的输入，至多存在一个中枢整数。

示例 1：

**输入：** n = 8
**输出：** 6
**解释：** 6 是中枢整数，因为 1 + 2 + 3 + 4 + 5 + 6 = 6 + 7 + 8 = 21 。

示例 2：

**输入：** n = 1
**输出：** 1
**解释：** 1 是中枢整数，因为 1 = 1 。

示例 3：

**输入：** n = 4
**输出：** -1
**解释：** 可以证明不存在满足题目要求的整数。

提示：

  • 1 <= n <= 1000

方法一：数学

思路与算法

记从正整数 x 加到正整数 y，y \ge x 的和为

sum}(x, y) = x + (x + 1) + \cdots + y

由「等差数列求和公式」得

sum}(x, y) = (x + y) \times (y - x + 1)}{2

则题目等价于给定一个正整数 n，判断是否存在正整数 x 满足

sum}(1, x) = \textit{sum}(x, n)

进一步将上式化简得到

x = \sqrt{n^2 + n}{2}

若 x 不为整数则返回 -1，否则得到「中枢整数」x。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int pivotInteger(int n) {
        int t = (n * n + n) / 2;
        int x = sqrt(t);
        if (x * x == t) {
            return x;
        }
        return -1;
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
class Solution {
    public int pivotInteger(int n) {
        int t = (n * n + n) / 2;
        int x = (int) Math.sqrt(t);
        if (x * x == t) {
            return x;
        }
        return -1;
    }
}
[sol1-Python3]
1
2
3
4
5
6
7
8
class Solution:
    def pivotInteger(self, n: int) -> int:
        t = (n * n + n) // 2
        x = int(t ** 0.5)
        if x * x == t:
            return x
        return -1

[sol1-Go]
1
2
3
4
5
6
7
8
func pivotInteger(n int) int {
    t := (n * n + n) / 2
    x := int(math.Sqrt(float64(t)))
    if x * x == t {
        return x
    }
    return -1
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
var pivotInteger = function(n) {
    let t = (n * n + n) / 2;
    let x = parseInt(Math.sqrt(t));
    if (x * x === t) {
        return x;
    }
    return -1;
};
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
public class Solution {
    public int PivotInteger(int n) {
        int t = (n * n + n) / 2;
        int x = (int) Math.Sqrt(t);
        if (x * x == t) {
            return x;
        }
        return -1;
    }
}
[sol1-C]
1
2
3
4
5
6
7
8
int pivotInteger(int n) {
    int t = (n * n + n) / 2;
    int x = sqrt(t);
    if (x * x == t) {
        return x;
    }
    return -1;
}

复杂度分析

  • 时间复杂度：O(1)，其中计算平方根有专门对应的 CPU 指令，可看作 O(1) 时间复杂度。
  • 空间复杂度：O(1)，仅使用常量空间。
 Comments
On this page
2485-找出中枢整数