[2024] 3/13 Leetcode Daily Challenge 2485. Find the Pivot Integer

2485. Find the Pivot Integer

코드

해설

문제에서 제시하는 Pivot Integer는
1 ~ x 까지의 합 = x ~ n 까지의 합 일때의 x 값이다.

예시)

1 2 3 4 5 6 7 8
		  x   n
          
Explanation: 6 is the pivot integer since: 1 + 2 + 3 + 4 + 5 + 6 = 6 + 7 + 8 = 21.

고등학생 때 배웠던 등차 수열을 이용하면 쉽게 풀린다.

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

분모 2를 지워주면,

$(1+x)\times x = (x+n)\times (n - x + 1)$

해당 식을 이용해서 코드를 짜면 된다.

for x in range(1, n+1):
	if (1 + x) * x == (x + n) * (n - x + 1):
    	return x

시간 복잡도

단순 계산이므로 O(1)