Sherlock and Array

Sort by

recency

|

964 Discussions

|

  • + 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";
    }
    
  • + 0 comments

    Here is my c++ solution, you can watch the explanation here : https://youtu.be/-kwepBHt_jM

    string balancedSums(vector<int> arr) {
        int ls = 0, rs = accumulate(arr.begin(), arr.end(), 0);
        for(int i = 0; i < arr.size(); i++){
            rs -= arr[i];
            if(i != 0) ls += arr[i-1];
            if(ls == rs) return "YES";
        }
        return "NO";
    }
    
  • + 0 comments

    Perl solution:

    sub balancedSums {
        my $arr = shift;
        
        my $total_sum = sum(@$arr);
        my $left_sum = 0;
        foreach my $num (@$arr) {
            my $right_sum = $total_sum - $left_sum - $num;
            return "YES" if $left_sum == $right_sum;
            $left_sum += $num;
        }
        return "NO";  
    }
    
  • + 0 comments

    Java:

    public static String balancedSums(List<Integer> arr) {
      int sum = 0;
      for (int i : arr) {
        sum += i;
      }
      int left = 0;
      for (int i = 0; i < arr.size(); i++) {
        int right = sum - left - arr.get(i);
        if (right == left) {
          return "YES";
        }
        left += arr.get(i);
      }
      return "NO";
    }
    
  • + 0 comments

    Here is the solution in Py3

    #!/bin/python3
    
    import math
    import os
    import random
    import re
    import sys
    
    # 
    #Complete the 'balancedSums' function below.
    #
    # The function is expected to return a STRING.
    # The function accepts INTEGER_ARRAY arr as parameter.
    #
    for t in range(int(input())):
        n = int(input())
        a = [int(b) for b in input().split()]
        s = sum(a)
        count = 0
        for i in range(n):
            if 2*count == s-a[i]:
                print("YES")
                break
            count += a[i]
        else:
            print("NO")