2485.找出中枢整数

【LetMeFly】2485.找出中枢整数

力扣题目链接：https://leetcode.cn/problems/find-the-pivot-integer/

给你一个正整数 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

方法一：数学

如果“1 和 x 之间的所有元素之和等于 x 和 n 之间所有元素之和”，

那么有：

$$1 + 2 + 3 + … + x = x + (x + 1) + … + n$$

于是有：

$$\frac{x * (x + 1)}{2} = \frac{(n - x + 1) * (x + n)}{2}$$

解得：

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

因为$n^2 + n=n(n+1)$一定是偶数，所以其一定能整除$2$。

我们只需要判断一下$\frac{n^2 + n}{2}$是否是平方数就好了

• 时间复杂度$O(1)$
• 空间复杂度$O(1)$

AC代码

C++

/*
1 + 2 + 3 + ... + x = x + (x + 1) + ... + n

x * (x + 1) / 2 = (n - x + 1) * (x + n) / 2

x * (x + 1) = (n - x + 1) * (x + n)

x^2 + x = nx - x^2 + x + n^2 - nx + n

2x^2 = n^2 + n

x = sqrt((n^2 + n) / 2)

n^2 + n = n(n + 1)一定是偶数，能整除2

就看n^2 + n是不是平方数了
*/

class Solution {
public:
    int pivotInteger(int n) {
        int ans = sqrt((n * n + n) / 2);
        return ans * ans == (n * n + n) / 2 ? ans : -1;
    }
};

Python

# from math import sqrt

class Solution:
    def pivotInteger(self, n: int) -> int:
        ans = int(sqrt((n * n + n) / 2))
        return ans if ans * ans == (n * n + n) / 2 else -1

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/131391141