CODEWITHSUNDEEP
python
ganeshram
ganeshram

Reputation: 127

How to make my Python code more time efficient?

The program I tried to execute has following problem statement:

The program must accept N integers containing integers from 1 to N with duplicates in any order. The program must print the missing integers from 1 to N among the given integers in ascending order as the output.

example :

Input: 5

2 5 5 1 1

Output: 3 4

Explanation: The integers 3 and 4 are missing in the 5 integers 2 5 5 1 1. Hence 3 and 4 are printed as the output

My code :

def modusoperandi(n, t):
    if str(n) not in t:
        yield n 

n = int(input())
t = tuple(sr for sr in input().split())
for i in range(1,n+1):
    for j in modusoperandi(i,t):
        print(j,end=' ')

My code, however, failed to pass all the test cases since it is takes considerable amount of time to execute for test cases with huge input[takes more than 500 ms which is the time limit].

I tried to compute execution time using timeit method. It is peculiar that when number of elements in tuple increase the execution time also increase for a given N. I prefered tuple over list since it is supposed to be more efficient.

Upvotes: 1

Views: 108

Answers (4)

Alain T.
Alain T.

Reputation: 42143

The key is indeed to use a set for checking the presence of expected numbers in the input string. You don't need to convert the input to integers though. You can do this the other way around by generating sequential numbers as strings. 

nums    = input().split()
numSet  = set(nums)
missing = " ".join(str(n) for n in range(1,len(nums)+1) if str(n) not in numSet)

print(missing) # 3 4

For this particular problem, there is a slightly faster alternative to using a set because you can afford to create an array of flags with a known (and reasonable) size:

numbers = input().split()
present = [False]*len(numbers)
for n in numbers: present[int(n)-1] = True
missing = " ".join(str(n+1) for n,seen in enumerate(present) if not seen)

Upvotes: 1

Michael Veksler
Michael Veksler

Reputation: 8475

You should think of the complexity of your solution (which is quite bad):

def modusoperandi(n, t):
    # Since 't' is a tuple, the complexity of 'not in t' is O(len(t))
    # This makes the overall complexity of this function O(len(t))
    if str(n) not in t:
        yield n 

n = int(input())
t = tuple(sr for sr in input().split()) # O(len(t))
for i in range(1,n+1):  # O(n) iterations

    # 0 or 1 iteration, but the call to 'modusoperandi' is O(len(t))
    for j in modusoperandi(i,t):  
        print(j,end=' ')

Overall complexity O(n * len(t)). This is not a very nice complexity. You'd like to have a complexity which is linear in the input. There are two ways:

  1. Use a hash table to mark all visited integers, and set is such a hash-table. Unfortunately hash-tables have some shortcomings.
  2. Since there are n entries and the numbers are in the range 1..n, then it is very efficient to use a characteristic vector values_encountered, in which values_encountered[i] is True if and only if i value was encountered. For big input, of this kind, this solution is likely to run faster than a set, and to consume less memory.

.

import numpy as np
n = int(input())

values_encountered = np.zeros(n+1, dtype=bool)     # O(n)
values_encountered[[int(i) for i in input().split()]] = True # O(n)
# Or:
# values_encountered[list(map(int, input().split()))] = True

values_missing= (values_encountered == False) # O(n)
values_missing[0] = False
print(*list(*values_missing.nonzero())) # O(n)

Upvotes: 0

Andrej Kesely
Andrej Kesely

Reputation: 195408

n = '5'
i = '2 5 5 1 1'

def compute(n, i):
    s1 = set(range(1, n+1))
    yield from sorted(s1.difference(i))


for val in compute(int(n), map(int, i.split()) ):
    print(val, end=' ')

Prints:

3 4

Upvotes: 0

AKX
AKX

Reputation: 168843

You'll want to convert the existing numbers into integers, then put them in a set; sets are very efficient for figuring out whether or not a given value is a member.

n = int(input())
extant = set(int(n) for n in input().split())
for i in range(1, n + 1):
    if i not in extant:
        print(i, end=" ")

Upvotes: 5

Related Questions