0

I'm trying to solve a coding problem for Hackerrank but continuously run into timeout errors for my code taking too long to run. I know that it works perfectly fine, indentation is not the problem, there is nothing 'wrong' with the code at all. I just need tips on how I can make it run more efficiently:

def main(n, o, q, m): 
    for x in m:
        for y,z in enumerate(o):
            x -= z
            if x<=0:
                print y+1
                break
        if x>0: print -1

o and m are a list of integers that are looped through subtracting the values of o from m until m is less than 0, the loop finishes and m is still not less than 0 it will print -1. The ultimate goal is to find which int from o finishes m.

Kayvia
  • 3
  • 3
  • You could pre-compute the partial sums of `o`. – Peter Wood Feb 09 '20 at 23:27
  • fix the indent for `if x> 0 : ....` and what exactly will you be trying to `break` out of the loop for, do you want to execute both if statements if not remove `break` and the print statements need `()` around them – de_classified Feb 09 '20 at 23:28
  • @PeterWood I can't pre-compute because I need to obtain the index at which the amount was finished. – Kayvia Feb 09 '20 at 23:49
  • @FishingCode Ive update the question, I would break out of the loop once I find the value that finishes m, the ```ifx>0: ...``` is if the value for m is not finished after the loop it will print -1 – Kayvia Feb 09 '20 at 23:51
  • Can the question be reopened? I think I've made it more focused. – Kayvia Feb 09 '20 at 23:58
  • ok, what is the correlation between x,y,z and m, if m is still not lesser than 0, than print -1 so remove the `if x>0:` statement...but again the correlation/details are unknown till we know more about the question – de_classified Feb 10 '20 at 00:01
  • @PaulRooney Yes, I only want to come out of the inner loop so that it will go to the next m value. The hackerrank is: [link](https://www.hackerrank.com/contests/uwi-comp2211-2020-potw-02/challenges/boss-business) – Kayvia Feb 10 '20 at 00:25
  • @FishingCode x is used to go through the values in m, and y,z are used to get the index and value of the values in o. I don't want to print -1 everytime the value for m is not less than 0, only after it's gone through the inner loop and subtracted all the values do I want it to print that it is '-1' if m is less than 0. This is the link to the problem: [link](https://www.hackerrank.com/contests/uwi-comp2211-2020-potw-02/challenges/boss-business) – Kayvia Feb 10 '20 at 00:28
  • @Kayvia The index of the finishing partial sum is the same as the index of the finishing amount. Honestly, think about it a bit. Also, see [**`itertools.accumulate`**](https://docs.python.org/3.2/library/itertools.html#itertools.accumulate) – Peter Wood Feb 10 '20 at 08:15
  • Can values of `o` be negative? – Peter Wood Feb 10 '20 at 08:30

1 Answers1

0

You are performing subtractions using o for every loop of m.

To improve performance you need to either loop m less or loop o less.

One way of looping o less is to pre-calculate all the partial sums.

x is having values from o subtracted. Perhaps you'll only subtract one number, or two, or a thousand. Who knows? And you will do so for every loop of m.

For example if x were 10, and o were [2, 4, 6, 8], the third term would be what finished the loop, the third term being 12, the sum of 2, 4, and 6.

Building a list of partial sums means the addition will only need to be done once.

itertools.accumulate can do this for you.

If o values can be positive or negative then you'll need to do a linear search as the partial sum won't be in ascending order. (Maybe there's a clever data structure you can use, but I don't know it.)

However if o values are all positive you could do a binary search of the partial sums.

See this answer to Python binary search-like function to find first number in sorted list greater than a specific value

Peter Wood
  • 23,859
  • 5
  • 60
  • 99