Finding the distance between every indices in an array that contain odd numbers

Question

I'm doing this HackerRank problem which basically boils down to what I've written in the title. We have to find out the distance between all the odd values in the array. I've written this code below which passes all the test cases but I think I can do better, namely, I don't have to make a separate array (oddindices) to contain the odd values' indices.

def min_bread(N, breads):
    oddcount = 0
    oddindices = []
    for idx in xrange(N):
        if breads[idx]%2:
            oddcount += 1
            oddindices.append(idx)
    if oddcount%2: # Odd number of odd loaves make it impossible to distribute
        return "NO"
    if oddcount==N or oddcount == 0: # All are odd (return that number) or even (return 0)
        return oddcount
    loaves = 0
    for idx in xrange(0, oddcount, 2):
        loaves += (oddindices[idx+1] - oddindices[idx])*2
    return loaves

if __name__ == '__main__':
    N = int(raw_input())
    breads = map(int, raw_input().split())
    print min_bread(N, breads)

But I can't figure out how to do it without having a separate array. The way I'm thinking is, if I encounter an odd value, I make the loop skip to AFTER the next odd value. I could do this easily with oddindices, but how do I do it without that extra array?

Answer 1

Code organisation

You've separated the input/output from the actual algorithm and that's a very nice thing that is not done as often as it should be in questions tagged with programming-challenge.

The only thing I'd change about the way you've done this is that the min_bread function does not need to be provided the N value as it should correspond to the length of the breads argument.

Loop like a native

I highly recommand Ned Batchelder's excellent talk called "Loop Like A Native". Among other things, it tells you that in general, you should not use a combination of range (or xrange) and len to iterate over something.

At this stage, the code looks like:

def min_bread(breads):
    oddcount = 0
    oddindices = []
    for i, val in enumerate(breads):
        if val % 2:
            oddcount += 1
            oddindices.append(i)
    # Odd number of odd loaves make it impossible to distribute
    if oddcount % 2:
        return "NO"
    # All are odd (return that number) or even (return 0)
    if oddcount==len(breads) or oddcount == 0:
        return oddcount
    loaves = 0
    for idx in xrange(0, oddcount, 2):
        loaves += (oddindices[idx+1] - oddindices[idx])*2
    return loaves

Details

You don't need to compute oddcount as you build oddindices, you can simply do oddcount = len(oddindices) after the loop.

Also, now you have a nice way to initialise oddindices. Indeed, in Python, the pattern l = []; for i in iter: if filter(i): l.append(func(i)) can be rewritten using a structure called "list comprehension" to get : l = [func(i) for i in iter if filter(i)].

In your case, you get:

oddindices = [i for i, val in enumerate(breads) if val % 2]
oddcount = len(oddindices)

Multiply once

You multiply by 2 each value you add to loaves. You could do it only once at the very end.

Sum builtin

You could use the sum builtin to perform the sums efficiently.

You'd get something like:

return 2 * sum(oddindices[idx+1] - oddindices[idx] for idx in xrange(0, oddcount, 2))

Then, the whole code looks like:

def min_bread(breads):
    oddindices = [i for i, val in enumerate(breads) if val % 2]
    oddcount = len(oddindices)
    # Odd number of odd loaves make it impossible to distribute
    if oddcount % 2:
        return "NO"
    # All are odd (return that number) or even (return 0)
    if oddcount==len(breads) or oddcount == 0:
        return oddcount
    return 2 * sum(oddindices[idx+1] - oddindices[idx] for idx in xrange(0, oddcount, 2))

Avoiding the additional array

A different way to write this without an additional array is to see that the different indices of odd values are substracted, then added, then substracted, etc. Also, you have to perform as many additions as substractions. We could use a simple flag to handle both the alternance of sign and the check that we've performed the same number of additions and substractions. For instance (highly not tested):

def min_bread(breads):
    sign = -1
    loaves = 0
    for i, val in enumerate(breads):
        if val % 2:
            loaves += sign * i
            sign *= -1
    return "NO" if sign == 1 else 2 * loaves