2485. 找出中枢整数

题目描述

给你一个正整数 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
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


func pivotInteger(n int) int {
    prefix, suffix := make([]int, n+1), make([]int, n+2)
    for i := 1; i <= n; i++ {
        prefix[i] = prefix[i-1] + i
        suffix[n-i+1] = suffix[n-i+2] + n - i + 1
    }
    for i := 1; i <= n; i++ {
        if prefix[i] == suffix[i] {
            return i
        }
    }
    return -1
}

优化：可以使用总和以及前缀和这两个条件来优化掉后缀和。代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


func pivotInteger(n int) int {
    prefix, sum := make([]int, n+1), 0
    for i := 1; i <= n; i++ {
        prefix[i] = prefix[i-1] + i
        sum += i
    }
    for i := 1; i <= n; i++ {
        if prefix[i-1] == sum-prefix[i] {
            return i
        }
    }
    return -1
}

解法二：数学

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
}