Find number of positives in segment of list

Timur Shleminov 0
Viewed 38

I have a unsorted list. I'm asked to print k-times number of positive values in a segment.The boarders for segment start with 1 not 0. So, if the boarder [1,3] it means that we should find all positives among elements with indices [0,1,2]

For example,

2 -1 2 -2 3
4
1 1
1 3
2 4
1 5

The answer needs to be:

1
2
1
3

Currently, I'm creating a list with length as original where i equals 1 if original is positive and 0 if original is negative or zero. After that I sum for this segment:

lst = list(map(int, input().split()))
k = int(input())

neg = [1 if x > 0 else 0 for x in lst]
for i in range(k):
    l,r = map(int, input().split())
    l = l - 1
    print(sum(neg[l:r]))

Despite the fact that it's the fastest code that I created so far, it is still too slow for this task. How would I optimize it (or make it faster)?

segment list python
1 Answers

If I understand you correctly, there doesn't seem to be a lot of room for optimization. The only thing that comes to mind really is that the lst and neg steps could be combined, which would save one loop:

positive = [int(x) > 0 for x in input().split()]
k = int(input())
for i in range(k):
    l, r = map(int, input().split())
    print(sum(positive[l-1:r]))

We can just have bools in the positive list, because bool is just a subclass of int, meaning True is treated like 1 and False like 0. (Also I would call the list positive instead of neg.)

The complexity is still O(n) though.

Daniil Fajnberg0
Related