推 NTUEE2CS: 大師 03/13 09:29
推 JIWP: 大師 03/13 09:34
推 sustainer123: 大師 我只想到第一種解法 03/13 09:55
https://leetcode.com/problems/find-the-pivot-integer
2485. Find the Pivot Integer
給定一個數字n，找出一個介於1~n的數字k滿足 1+2+...+k = k+(k+1)+(k+2)+...+n，如
果不存在返回-1。
思路：
1.先求1~n的和
2.再遍歷一次1~n把pivot放進去判斷
pycode:
------------------------------------------
class Solution:
def pivotInteger(self, n: int) -> int:
all = sum([i for i in range(1, n + 1)])
curr = 0
for i in range(1, n + 1):
curr += i
if all == curr:
return i
all -= i
return -1
------------------------------------------
數學解:
1.假設p=piovt
(1+p)p/2 = (p+n)(n-p+1)/2
(1+p)p = (p+n)(n-p+1)
p + p^2 = pn + n^2 - p^2 - np + p + n
p^2 = n^2 - p^2 + n
p^2 = (n^2 + n) / 2
p = sqrt((n^2 + n) / 2)
套公式看開根能不能開出一個合法值就可以判斷
pycode:
------------------------------------------
class Solution(object):
def pivotInteger(self, n):
x = sqrt(n * (n + 1) / 2)
if x % 1 != 0:
return -1
else:
return int(x)
------------------------------------------
--
https://i.imgur.com/AhrL1pB.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.138.199.37 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1710293197.A.A32.html