Return index of array where sum first passes n 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 &lt;= 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.
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 &gt; target Then
            getPositionFromSum = index + 1
            Exit For
        End If
    Next

End Function