Facebook | Training | Balanced Split

Hi,
I've solved it, but not able to solved with complexity lower than O(nlog N)m, because of sorting. Maybe somedy smarter than me show me better solution.

Looks like following leetcode: https://leetcode.com/problems/partition-equal-subset-sum/

Balanced Split

Given a set of integers (which may include repeated integers), determine if there's a way to split the set into two subsets
A and B such that the sum of the integers in both sets is the same, and all of the integers in A are strictly smaller than all of the integers in B.
Note: Strictly smaller denotes that every integer in A must be less than, and not equal to, every integer in B.
Signature
bool balancedSplitExists(int[] arr)
Input
All integers in array are in the range [0, 1,000,000,000].
Output
Return true if such a split is possible, and false otherwise.

*Example 1
arr = [1, 5, 7, 1]
output = true
We can split the set into A = {1, 1, 5} and B = {7}.
*

Example 2
arr = [12, 7, 6, 7, 6]
output = false
We can't split the set 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.
*

func balancedSplitExists(arr []int) bool {
	var leftSum, rightSum int

	sort.Ints(arr)
	for i:=0; i < len(arr); i++ {
		leftSum += arr[i]
	}

	for i:=len(arr)-1; i >= 0;i-- {
		leftSum -= arr[i]
		rightSum += arr[i]
		if leftSum == rightSum {
			if arr[i-1] < arr[i] {
				return true
			}
		}
	}

	return false
}

Unit Test

func Test_Partition_Equal_Subset_Sum(t *testing.T) {
	testDatas := []struct{
		nums []int
		result bool
	} {
		{ []int{1, 5, 7, 1}, true},
		{ []int{12, 7, 6, 7, 6}, false},
		{ []int{}, false},
		{ []int{ 2,}, false},
		{ []int{20, 2,}, false},
		{ []int{5,7,20,12,5,7,6,14,5,5,6,}, true},
		{ []int{5,7,20,12,5,7,6,7,14,5,5,6,}, false},
		{ []int{1,1,1,1,1,1,1,1,1,1,1,1,}, false},
	}

	for _, td := range testDatas {
		r := balancedSplitExists(td.nums)
		if r != td.result {
			t.Errorf("Source: %d n Expected:%v \n Actual:  %v\n",
				td.nums,
				td.result,
				r)
		}
	}
}
Comments (50)