Sherlock and Array

  • + 0 comments

    Linear scan

    1. Time complexity: O(n)
    2. Space complexity: O(1)
    int sum_up(int* arr, int l, int r){
        int res = 0;
        for (int i = l; i<= r; i++){
            res += arr[i];
        }
        return res;
    }
    
    char* balancedSums(int arr_count, int* arr){
        int total_sum = sum_up(arr, 0, arr_count-1);
        int left_sum = 0;
        int right_sum;
        for (int i=0; i<arr_count; i++){
            right_sum = total_sum - left_sum - arr[i];
            if (left_sum == right_sum){
                return "YES";
            }
            left_sum += arr[i];
        }    
        return "NO";
    }