Return index of array where sum first passes n

Question

I have an array of integers and a number n. I want to sum the elements of the array and return the index where the sum passes n, as efficiently as possible.

For example, assume:

theString = "6-7-7-10-7-6"
theNumber = 33

expected result: 5

This does the trick but not very efficiently: (and error prone; will check for errors when I've found the best solution)

Public Function getIndexFromSum(theString As String, theNumber As Integer) As Integer
    Dim theSides As Variant
    Dim sum As Integer
    Dim index As Integer

    theSides = Split(theString, "-")

    While sum <= theNumber
        sum = sum + theSides(index)
        index = index + 1
    Wend

    getIndexFromSum = index
End Function

I haven't been able to describe this to google succinctly enough to get any meaningful results, and searching for any combination of the keywords involved produces links to tons of unrelated stuff. I'm sure this problem will have been encountered before (and likely has a smart solution out there somewhere), but I haven't been able to find any sites that can help.

Any help/advice would be very much appreciated!

EDIT - more info

1) theString will always be stored in the format "x-x-x".

2) theNumber will always be smaller than or equal to the sum of the numbers in theString.

3) The length of theString will be short - usually between 2 and 10 numbers, each less than 100.

4) The function will be called with small inputs, but many times. Low overhead is top priority.

Answer 1

One inefficient line of code is this one:

Split(theString, "-")

It's slow because:

• It splits the entire string, even though you're only interested in the first part of the string.
• It allocates a new array and creates many new string objects, instead of parsing the existing string in-place.

Therefore a faster algorithm, if the string is longer than you need, might be:

   while not found
       look for the next hyphen
       get the substring up to the next hyphen
       convert the substring to an integer
       add the number
       exit the loop if the sum is large enough

However, if you need to parse the whole (or most of) the string, the implementation of Split might be faster than your implementation of the above algorithm.

---

Another possible inefficiency is the conversion from string to number. My guess is that VB.NET implicitly uses CInt which is a complicated function. Another method like Convert.ToInt32 or Int32.Parse might be faster, but even that might be slow because, according to MSDN,

"... value is interpreted by using the formatting conventions of the current thread culture."

Other people get faster results by writing their own converters.

---

In summary (further to Comintern's suggestion) I suspect that something like the following would be faster (forgive me if I code this in C# instead of VB) (untested code ahead):

int number = 0;
int total = 0;
int count = 0;
foreach (char c in theString) // For Each c As Char in theString
{
    if (c == '-')
    {
        total = total + number;
        if (total > theNumber)
            return count;
        // else prepare for the next number
        count = count + 1;
        number = 0;
    }
    else
    {
        // continue to parse this number
        // assume that c is an ASCII digit
        int digit = (c - '0'); // But is converting char to int slow or difficult?
        number = (10 * number) + digit;
    }
}

// didn't find the number; return count anyway?
return count;

Answer 2

I'm not sure what you mean by "This does the trick but not very efficiently". I don't really see a way to make the algorithm more efficient, as it is just making a single pass over the array and exits early when it gets the answer. If the input is really long, you could convert it to a byte array instead of splitting it to cut down on the casts, but then you would have to nest the loops, add a subtraction to convert the ascii codes to numbers, add multiplications to keep track of multiples of 10, etc. This would likely be a lot slower than the current method unless you were working with strings on the order of kilobytes.

That said, a couple of observations about the code. I'd personally use a For loop instead of a While loop to prevent you from running outside of the array bounds for inputs where the target number you are looking for is higher than the sum of the complete array. For example, with the input string of "6-7-7-10-7-6", a target higher than 43 will overrun the array bound and throw an error. You'll get a similar error if it is passed an empty string (Split will happily give you an array with an upper bound of -1 in that case).

Also note that you are not returning the zero based index, you are returning the one based position of the token in the string. If this is the desired behavior, I'd rename the function to make it obvious that you can't use the return value to index into the array.

About the only thing that I would do to make this a tiny bit more efficient would be to use a String array instead of a Variant and use explicit casting so the run-time doesn't have to resolve the Variants for you more than once. Even this improvement will likely be unnoticeable on any reasonable sized input (you'll overflow an Integer long before you'd notice the performance increase anyway).

Maybe something like this:

Public Function getPositionFromSum(source As String, target As Integer) As Integer

    Dim sides() As String
    Dim sum As Integer
    Dim index As Integer

    getPositionFromSum = -1    'Or whatever the "not found" condition is.
    sides = Split(source, "-")

    For index = 0 To UBound(sides)
        sum = sum + CInt(sides(index))
        If sum > target Then
            getPositionFromSum = index + 1
            Exit For
        End If
    Next

End Function