Algorithm: Array Summary Threshold

3 minutes read
Algorithm • Programming
Algorithm • Golang • Programming • Testing

Question

Given an array of integers $A (a_i \geq 0, i \in [0, n])$ and a threshold $T$.

If $\sum_{i = 0}^n a_i > T$, find an integer $t$, for $a_i > t (i \in [0, n]) \to a_i = t$.

Find the largest $t$ which makes $\sum_{i = 0}^n a_i \leq T$.

For Example, $A = [30, 20, 10, 50, 40],,,T = 127$. Expecting $t = 33$.

Answer

ArraySummaryThreshold.go

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

package algorithms

import "sort"

// ArraySummaryThreshold - Find the threshold for array A
func ArraySummaryThreshold(A []int, T int) (t int) {
	// If the array is empty, return 0.
	length := len(A)
	if length == 0 {
		return 0
	}

	sum := 0
	for _, a := range A {
		sum += a
	}

	// If the summary <= T, return the max element of A.
	if sum <= T {
		t = 0
		for _, a := range A {
			if a > t {
				t = a
			}
		}
		return t
	}

	// Sort the array
	sort.Ints(A)

	sum = 0
	for i, a := range A {
		// Assume t = a and check summary
		if sum+a*(length-i) > T {
			// Calculate t
			t = (T - sum) / (length - i)
			break
		}

		sum += a
	}

	return t
}

Test

ArraySummaryThreshold_test.go

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

package algorithms

import "testing"

var tests = []struct {
	A []int
	T int
	t int
}{
	{[]int{}, 200, 0},                    // Empty array
	{[]int{10, 20, 30, 40, 50}, 200, 50}, // Summary < T, ordered
	{[]int{30, 20, 10, 50, 40}, 200, 50}, // Summary < T, unordered
	{[]int{10, 20, 30, 40, 50}, 150, 50}, // Summary = T, ordered
	{[]int{30, 20, 10, 50, 40}, 150, 50}, // Summary = T, unordered
	{[]int{10, 20, 30, 40, 50}, 0, 0},    // T = 0
	{[]int{10, 20, 30, 40, 50}, 128, 34}, // Summary > T, found max t which make summary = T
	{[]int{10, 20, 30, 40, 50}, 127, 33}, // Summary > T, found max t which make summary < T
	{[]int{10, 20, 30, 40, 50}, 4, 0},    // Summary > T, t = 0
	{[]int{30, 20, 10, 50, 40}, 127, 33}, // Unordered
}

func TestArraySummaryThreshold(t *testing.T) {
	for _, test := range tests {
		out := ArraySummaryThreshold(test.A, test.T)
		if out != test.t {
			t.Errorf("Test: %v\nUnexpected result: %d", test, out)
		}
	}
}

Run test.

1
2
3

$ go test -run TestArraySummaryThreshold
PASS
ok  	_/Users/mingjie/Documents/Development	0.011s