algorithm - Finding sum of N largest elements of array of single-digit values

Possible Duplicate:

Retrieving the top 100 numbers from one hundred million of numbers

I have a array which consists positive number between 0 to 9,(digit can repeat). I want to find sum of N largest elements

``For example array = 5 1 2 4 and N=2ans = 5+4 = 9``

Simple approach: sort array and find sum of n largest elements. But i dont want to use it

The simplest O(n) solution is the following:

1. Run through array `a` and increasе `b[a[i]]` where `b` is a zero initialized array of 10 integers.
2. Run through `b` starting from the end (9th position) and if `b[i]` is lower than `N` add `b[i] * i` to your answer, then decrease `N` by `b[i]`, otherwise if `b[i]` is greater or equal to `N` add `N * i` to the answer and over the loop.

Edit: code

``````vector<int> b(10, 0);
for(int i = 0; i < a.size(); ++i) {
b[a[i]]++;
}

int sum = 0;
for(int i = 9;  i >= 0; --i) {
if(b[i] < n) {
sum += b[i] * i;
n -= b[i];
} else {
sum += n * i;
n = 0;
break;
}
}
if(n != 0) {
// no enough element in the array
}
``````

insert all into a heap, and then delete (and sum) N elements.
complexity: `O(n+Nlogn)`, because creating a heap is O(n), and each delete is O(logn), and you iterate over delete N times. total: O(n+Nlogn) [where n is the number of elements in your array].

EDIT: I missed it at first, but all your numbers are digits. so the simplest solution will be using radix sort or bucket sort and then sum the N biggest elements. solution is O(n).

I am a bit slow today, should code faster hehe ;-)

There are multiple answers already but I want to share my pseudo-code with you anyway, hope it helps!

``````public class LargestSumAlgorithm
{
private ArrayList arValues;

{
}

public int ComputeMaxSum(int p_iNumOfElementsToCompute)
{
// check if there are n elements in the array
int iNumOfItemsInArray = arValues.Size;
int iComputedValue = 0;

if(iNumOfItemsInArray >= p_iNumOfElementsToCompute)
{
// order the ArrayList ascending - largest values first
arValues.Sort(SortingEnum.Ascending);
// iterate over the p_iNumOfElementsToCompute in a zero index based ArrayList
for(int iPositionInValueArray = 0; iPositionInValueArray < p_iNumOfElementsToCompute); iPositionInValueArray++)
{
iComputedValue += arValues[i];
}
}
else
{
throw new ArgumentOutOfRangeException;
}

return iComputedValue;
}

public LargestSumAlgorithm()
{
arValues = new ArrayList();
}
}

public class Example
{
LargestNumAlgorithm theAlgorithm = new LargestSumAlgorithm();