# Leetcode: Split Array With Same Average

Split Array With Same Average Similar Problems:

In a given integer array A, we must move every element of A to either list B or list C. (B and C initially start empty.)

Return true if and only if after such a move, it is possible that the average value of B is equal to the average value of C, and B and C are both non-empty.

```Example :
Input:
[1,2,3,4,5,6,7,8]
Output: true
Explanation: We can split the array into [1,4,5,8] and [2,3,6,7], and both of them have the average of 4.5.
```

Note:

• The length of A will be in the range [1, 30].
• A[i] will be in the range of [0, 10000].Given an integer array of size n, find all elements that appear more than n/3 times. The algorithm should run in linear time and in O(1) space.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

```// Blog link: https://code.dennyzhang.com/split-array-with-same-average
// Basic Ideas: BFS pruning
// Observation:
//  avg(A) == avg(B) == avg(C)
//  We only need to check combination which has no more than len(A)/2 items.
//          Apparently max(len(B), len(C)) <= len(A)/2
//  Avoid duplicated caculation by using a hashmap
//  If we sort A, once avg(B) >= avg(A), we can't add any more item which is bigger than avg(A)
//
// Complexity:
import "sort"
type Entity struct {
count, sum int
}

func splitArraySameAverage(A []int) bool {
if len(A)<=1 { return false }

sum_a := 0
for _, v:= range A { sum_a+=v }
visited := map[Entity]bool{}

sort.Ints(A[:])
// count, sum
queue := [][]int{}
for _, v:= range A {
// add current item to queue
if v*len(A) == sum_a { return true }
entity := Entity{1, v}
if visited[entity] == false {
queue = append(queue, []int{1, v})
visited[entity] = true
}
// whether add current item to existings items in the queue
list := [][]int{}
for _, item:= range queue {
// whether to explore
if item*2<len(A) {
v1, v2:= (item+v)*len(A), (item+1)*sum_a
if v1==v2{
return true
} else {
if v1<v2 {
entity = Entity{item+1, item+v}
if visited[entity] == false {
list = append(list, []int{item+1, item+v})
visited[entity] = true
}
}
}
}
}
// update queue
for _, v:= range list { queue = append(queue, v) }
}
return false
}
```

Share It, If You Like It.