2485. Find the Pivot Integer

發表於 | 分類於

problem

solution

  • prefix sum
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    class Solution {
    public:
        int pivotInteger(int n) {
            if(n == 1) return n;
            int total = (n*(n+1))/2;
            int left = 0;
            for(int i=1;i<=n;++i){
                left +=i;
                if(left == total) return i;
                total-=i;
            }
            return -1;
        }
    };
  • binary search
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    class Solution {
    public:
        int pivotInteger(int n) {
            if(n == 1) return n;
            int total = (n*(n+1))/2;
            int l= 0, r = n-1;
            while(l<=r){
                int mid = l + (r-l)/2;
                int left = ((mid+1)*mid)/2;
                int right = (n+mid)*(n-mid+1)/2;
                if(left == right) return mid;
                else if(left < right) l = mid+1;
                else r = mid-1;
            }
            return -1;
        }
    };
  • Math
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    class Solution {
    public:
        int pivotInteger(int n) {
            int ans = (n*n+n)/2;
            int sq = sqrt(ans);
            if(sq * sq == ans)return sq;
            else return -1;
            return -1;
        }
    };

    analysis

  • prefix sum
    • time complexity O(n)
    • space complexity O(1)
  • binary search
    • time complexity O(logn)
    • space complexity O(1)
  • Math
    • time complexity O(sqrt(n))
    • space complexity O(1)