Reducing Run Time Complexity !!! Reducing Nested loops in Python

Question

I am working on the python program which gives/takes standard input/output. The first line gives Number of Test Cases T. Second-line gives the size of data N. Third and Fourth line gives space-separated integers respectively of length N. The program arranges Set A and B that Set A has the maximum number of items that are greater than their equally-indexed items in Set B. Below is my code:

 def main():
   T=int(input())
   for ii in range(T):
        N=int(input())
        revo=list(map(int, input().split()))
        star=list(map(int, input().split()))
        win=0
        for i in range(N):
            a=1
            for j in range(revo[i]):
                b=revo[i]-a
                if b in star:
                    win=win+1
                    t=star.remove(b)
                    break
                a=a+1
        print(win)
main()

The inputs are:

1
10
3 6 7 5 3 5 6 2 9 1
2 7 0 9 3 6 0 6 2 6

The output is 7 because when arranged optimally Set A has 7 items which are greater than in Set B. But when we input large datasets it took long time to produced output. Is there any better functions that I can use to Reduce Run Time?

RafalS · Accepted Answer · 2020-04-17 17:18:17Z

1

Your solution is O(k*n^2), which is really a lot.

 def main():
   T=int(input())
   for ii in range(T): # ignoring number of inputs in time complexity
        N=int(input())
        revo=list(map(int, input().split())) # O(n), doesn't matter
        star=list(map(int, input().split())) # O(n), doesn't matter
        win=0
        for i in range(N): # n
            a=1
            for j in range(revo[i]): # n*k, k depends on 
                                     # how big is each number, hard to tell
                b=revo[i]-a
                if b in star: # k*n^2
                    win=win+1
                    t=star.remove(b) # normally this would multiply by n, but
                                     # remove can be called at most n times 
                    break
                a=a+1
        print(win)
main()

You could gown down to O(nlogn) if you sorted both lists first. Here's my solution:

def solve(list1, list2):
    list1 = sorted(list1) # n*logn
    list2 = sorted(list2) # 2*n*logn
    pos_in_list1, pos_in_list2 = 0, 0
    while pos_in_list1 < len(list1): # 2*n*logn + n
        if list1[pos_in_list1] > list2[pos_in_list2]:
            pos_in_list1 += 1
            pos_in_list2 += 1
        else:
            pos_in_list1 += 1
    return pos_in_list2


print(solve([3, 6, 7, 5, 3, 5, 6, 2, 9, 1], [2, 7, 0, 9, 3, 6, 0, 6, 2, 6]))
# 7


def main():
    _ = input()  # we don't need n
    list1 = [int(i) for i in input().split()] # O(n), doesn't matter
    list2 = [int(i) for i in input().split()] # O(n), doesn't matter
    print(solve(list1, list2))

O(2*n*logn + n) = O(nlogn)

edited Apr 17, 2020 at 17:18

answered Apr 17, 2020 at 16:15

RafalS

6,5441 gold badge23 silver badges26 bronze badges

Sign up to request clarification or add additional context in comments.

10 Comments

VIKAS RATHEE Over a year ago

that's a good answer, but still, here time complexity is O(NxN), how can we reach up to O(nlogn)

RafalS Over a year ago

It's O(nlogn). I'll add comments about complexity

VIKAS RATHEE Over a year ago

you have inserted commas <,> in input, that means it became integer, but the input is actually a <str> the integers are only space-separated. First, we have to convert them to integers

VIKAS RATHEE Over a year ago

I have just integrated and complied it, it works fine on large data sets. Thank you

Tawy Over a year ago

Sure but it is still a O(n) operation, that is executed maximum n times during the program, so a total of O(n^2)

|

Collectives™ on Stack Overflow

Reducing Run Time Complexity !!! Reducing Nested loops in Python

1 Answer 1

10 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

10 Comments

Your Answer

Sign up or log in

Post as a guest

Related