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

Question

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=2
ans = 5+4 = 9

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

I think the limitation that elements are between 0 and 9 makes it not a close duplicate. There are more efficient answers here that take advantage of the restricted range. — AShelly, Jul 05 '11 at 19:05
This is *not* a duplicate of that other question due to the constraints. — FogleBird, Jul 06 '11 at 02:28

Mihran Hovsepyan · Accepted Answer · 2014-10-20T09:49:38.933

The simplest O(n) solution is the following:

Run through array a and increasе b[a[i]] where b is a zero initialized array of 10 integers.
Run through b starting from the end (9^th 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
}

+1. my solution didn't take advantage of the fact that all elements are 0-9, so a radix sort (which is O(n)) will do the trick. — amit, Jul 05 '11 at 18:26

amit · Answer 2 · 2011-07-05T18:29:03.680

1

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).

edited Jul 05 '11 at 18:29

answered Jul 05 '11 at 18:17

amit

175,853
27
231
333

what about inserting in BST and then traversing right root left, and decprementing N each time till i reach 0 – akshay Jul 05 '11 at 18:18
@akshay: inserting into a sort tree requires a sort, which will be O(nlogn), which is worth then O(n+Nlogn) – amit Jul 05 '11 at 18:20
1

@akshay's solution with sorting is better. – Mihran Hovsepyan Jul 05 '11 at 18:20
@Mihran: it results in worth performance for N << n (where n is the array's size) – amit Jul 05 '11 at 18:21
@amit and Mihran:So can i say that sorting approach is better then BST and bst is better then ur heap method – akshay Jul 05 '11 at 18:22
@akshay: NO. sorting and BST are equivalent, both are O(nlogn), where heap is O(n+Nlogn), and O(n+Nlogn) is better then O(nlogn) [n is the number of elements in the array] – amit Jul 05 '11 at 18:24
@all:can there be any methamathical approach ?BST approach doesnot take advantage of the fact that all nos are between 0 to 9 – akshay Jul 05 '11 at 18:31
@akshay: see my edit and @Mihran's answer, both are taking advantage of the facts that all elements are integers in the range [0,9] – amit Jul 05 '11 at 18:32
wht is array is already sorted?in this case will time complexity will be O(n)??? or O(n2) [ n square] – akshay Jul 05 '11 at 19:14
@akshay: if the array is already sorted, you just need to summarize N elements, it will be O(N), since N<=n it is indeed O(n) – amit Jul 05 '11 at 20:17

score 0 · Answer 3 · answered Jul 05 '11 at 18:44

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 void AddValueToArray(int p_iValue)
    {
        arValues.Add(p_iValue);
    }

    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();
    theAlgorithm.AddValueToArray(1);
    theAlgorithm.AddValueToArray(2);
    theAlgorithm.AddValueToArray(3);
    theAlgorithm.AddValueToArray(4);
    theAlgorithm.AddValueToArray(5);

    int iResult = theAlgorithm.ComputeMaxSum(3);
}

score 0 · Answer 4 · answered Jul 05 '11 at 21:16

0

If you are using C++, use std::nth_element() to partition the array into two sets, one of them containing the N largest elements (unordered). Selection algo runs in O(n) time.

answered Jul 05 '11 at 21:16

Akhil

2,269
6
32
39

The asker is looking for better approaches to the problem. "Use C++" isn't a real answer, especially considering he didn't tag his question with C++. – Jul 06 '11 at 01:24

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

4 Answers4