Given an array of integers (which may include repeated integers), determine if there's a way to split the array into two subsequences A and B such that the sum of the integers in both arrays is the same, and all of the integers in A are strictly smaller than all of the integers in B.

Example 1

arr = [1, 5, 7, 1] output = true

We can split the array into A = [1, 1, 5] and B = [7].

Example 2

arr = [12, 7, 6, 7, 6] output = false

We can't split the array into A = [6, 6, 7] and B = [7, 12] since this doesn't satisfy the requirement that all integers in A are smaller than all integers in B.

def f(arr):
    arr = sorted(arr)
    
    pos = 0
    sum_l, sum_r = 0, 0

    while pos < (len(arr)-1):
        sum_l, sum_r = sum(arr[:pos 1]), sum(arr[pos 1:])
        pos  = 1
        if sum_l == sum_r:
            return True
    return False

My thoughts are that sorting is O(nlogn), the while loop is O(n), then arr[:pos 1] is O(n) overall and arr[pos 1:] is also O(n) overall, so all together is O(nlogn) O(n*(n n)) = O(nlogn) O(n^2). Is that correct?

Also, is there a way to get rid of this slicing operator to reduce the complexity?

CodePudding user response：

A simple way to reduce complexity is to avoid repeated calculation at each iteration:

def foo(arr):
    arr = sorted(arr)
    sum_l = 0
    sum_r = sum(arr)
    for val in arr:
        sum_l  = val
        sum_r -= val
        if sum_l == sum_r:
            return True
    return False

However, its output is not correct for the second example. You may need to adjust your algorithm.