Find lost number in number sequence

Question

Okay so basically all i have to do is find a lost number in sequence.

For the input data:

5
2 3 1 5

The correct answer is

def findMissing(n):
    
    tempList = []
    for i in range(0, n-1):
        tempList.append(str(input()))
    return [x for x in range(tempList[0], tempList[-1]+1) if x not in tempList] 
    

findMissing(5)

Output:

---> 11     return [x for x in range(tempList[0], tempList[-1]+1) if x not in tempList]

TypeError: must be str, not int

I've tried something like that, i wanted to create a list, and input would be appearing into that list, then i will return the missing value from that list, but it's not working.

`input()` already gives you a `str` -- you want to convert it to an `int`. — Samwise, Mar 26 '21 at 19:34
Does this answer your question? [Get a list of numbers as input from the user](https://stackoverflow.com/questions/4663306/get-a-list-of-numbers-as-input-from-the-user) — 001, Mar 26 '21 at 19:35
Thanks @Samwise it solved my problem, and also my code is working! — KermitTheFrog, Mar 26 '21 at 19:36
sum(1...n) = n*(n+1)/2. So just sum the numbers you get from input and subtract from sum(1...n) — inspectorG4dget, Mar 26 '21 at 19:38
For the one-line solution: `print((set(range(1, int(input())+1)) - set(map(int, input().split()))).pop())` — Samwise, Mar 26 '21 at 20:07
yup, there's nothing in there that would result in every element of one set being compared against all the others or anything like that — Samwise, Mar 26 '21 at 21:04

Cory Kramer · Answer 1 · 2021-03-26T19:43:39.767

0

You could generate a set of the "full" sequence using range then take the set.difference with your given list of data, then that should contain the missing item.

def findMissing(n, data):
    return set(range(1, n+1)).difference(data).pop()

>>> findMissing(5, [2, 3, 1, 5])
4

Since you know the sequence is contiguous, you can also do this arthimetically

def findMissing(n, data):
    return sum(range(1,n+1)) - sum(data)

>>> findMissing(5, [2, 3, 1, 5])
4

edited Mar 26 '21 at 19:43

answered Mar 26 '21 at 19:33

Cory Kramer

114,268
16
167
218

And also i have one question, what is time complexity of this one? – KermitTheFrog Mar 26 '21 at 19:37
@Daro1234451 The long pole in the tent is likely `set.difference` which based on typical implementation is `O(n)` – Cory Kramer Mar 26 '21 at 19:38
I have also different question, what will be the O(1) solution? – KermitTheFrog Mar 26 '21 at 19:41
2

@Daro1234451 There is no `O(1)` solution – Cory Kramer Mar 26 '21 at 19:42
I don't know exactly why, I thought O(n) will be in the case i will use for loop or i will iterate over something, but even there? I also thought operations set and pop, works in O(1) complexity. Would you mind to explain? – KermitTheFrog Mar 26 '21 at 20:05
Okay i understand. Nevermind. Thanks for every help. – KermitTheFrog Mar 26 '21 at 20:15
hey is there a solution without using any python tools? Like arithmetic progression sum or something like this? – KermitTheFrog Apr 20 '21 at 08:07

score 0 · Answer 2 · answered Mar 26 '21 at 19:37

This error actually comes from this step:

tempList[-1]+1

The way to reproduce this would be:

'1' + 1
TypeError: must be str, not int

You need to add like types. You can fix it by doing int(input()) which will convert the string type to an int.

range will also throw an error on str arguments:

range('1', '3')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'str' object cannot be interpreted as an integer

So make sure you are giving it integer arguments.

Chiheb Nexus · Answer 3 · 2021-03-26T19:47:04.327

0

Another variant of @Cory Kramer answer using set symmetric difference:

def find_missing(number, data):
    return (set(data) ^ set(range(1, number + 1))).pop()

find_missing(5, [2, 3, 1, 5])

>> 4

Check the official documentation for more informations.

edited Mar 26 '21 at 19:47

answered Mar 26 '21 at 19:41

Chiheb Nexus

9,104
4
30
43

Find lost number in number sequence

3 Answers3