[LeetCode] 2485. Find the Pivot Integer

https://leetcode.com/problems/find-the-pivot-integer/description/

Leetcode - Find the Pivot Integer

문제 유형 : 수학

문제 난이도 : Easy

 

문제

Given a positive integer n, find the pivot integer x such that:

• The sum of all elements between 1 and x inclusively equals the sum of all elements between x and n inclusively.

Return the pivot integer x. If no such integer exists, return -1. It is guaranteed that there will be at most one pivot index for the given input.

 

자연수 n이 주어진다. 피벗 정수 x를 구해라

피벗은 1 ~ x까지의 합 = x부터 n까지의합을 만족하는 x를 만한다.

없으면, -1을 반환하라.

최대 1개가 나오도록 TC가 주어진다.

 

풀이

전체 합을 구해준다.

x = 1부터 n까지 대입해보면서, 양측의 값을 구해서 비교하고, 피벗이라면 반환한다.

양측의 값을 구하는 방법은 공식 n(n+1)/2를 이용하면 편하다.

1부터 x까지: x(x+1)/2

x부터 n까지: 전체합 - (1부터x까지의합) + x

 

반복문이 종료되면, -1을 반환한다.

 

코드

C++

class Solution {
public:
    int pivotInteger(int n) {
        if(n == 1) return 1;
        const int sum = n*(n+1)/2;

        for(int i = 1; i < n; i++) {
            int left = i*(i+1)/2;
            int right = sum - left + i;

            if(left == right) return i;
        }

        return -1;
    }
};