Instead of removing values from the array and recomputing the standard deviation, conceive an empty array, add values to it and compute the standard deviation using an updating formula.
The trick to this is to add the values in an ordering such that the standard deviation is non-decreasing as values are added. This can be accomplished by adding values that are closest to the mean of the original array. In other words, the values with the smallest absolute deviation from the mean.
So, the algorithm that should work:
- Compute mean of array
- Sort array comparing items by absolute deviation from the mean
- Set N = 2
- Compute the standard deviation for the first two elements
- While standard deviation < target standard deviation AND the array still has elements
- Set N = N + 1
- Take next item from array
- Recompute the standard deviation with the additional value using an updating formula
- If array still has elements return N
- Else return N - 1
Here is an example case to demonstrate the algorithm:
Source Array: [10, 14, 16, 18, 20, 22, 24]
Target SD: 2.5
Step 1) Mean = 17.0
Step 2) [16, 18, 14, 20, 22, 10, 24]
Step 4) SD([16,18]) = 1.4142
Step 5.2) SD([16,18,14]) = 2
Step 5.2) SD([16,18,14,20]) = 2.5820
Return 3