How to find the smallest missing numbers from a list without using inbuilt functions or modules

Question

Here is my list:

List = [[1,2,4,5], [1,2,3,4,5,7], [1,4,5,6], [2,3,5], [1,2,3]]

From this how to find all the smallest missing numbers?

Edit:

The "smallest missing number" is the first integer (> 0) that is not in the list.
The expected output for the example input is 3, 6, 2, 1 and 4.
The input lists are always sorted.

Please show the code that you've tried already. Also, it's not clear exactly what the problem is here... — Hayley Guillou, Aug 18 '15 at 06:31
*without any python inbuild functions* -- Does that mean no `for` loops, no addition and no Python? — ilent2, Aug 18 '15 at 06:40
Sounds like a homework assignment to keep you busy for a while. In a real-life situation you'd never avoid built-in functions for tasks like this. — Falko, Aug 18 '15 at 06:45
Will the lists always be sorted? And what if a list doesn't contain the `1`. Would `1` be the solution? — Falko, Aug 18 '15 at 07:01
@Falko Yeah i accept that, but i mean for range,sort like. and i hope you guys can understand the problem by the below answer :) — user458766, Aug 18 '15 at 07:01

Falko · Accepted Answer · 2015-08-18T07:09:28.467

2

An approach without any built-in functions:

Lists = [[1,2,4,5],[1,2,3,4,5,7],[1,4,5,6]]

for List in Lists:
    i = 1
    while i <= List[-1] + 1:
        if i in List:
            i += 1
        else:
            break
    print i

Basically it processes each List separately (is that what you want?). It iterates a counter i starting at 1 (assuming you look for integers > 0) and stops, as soon as List doesn't contain i.

Output:

3
6
2

edited Aug 18 '15 at 07:09

answered Aug 18 '15 at 06:59

Falko

17,076
13
60
105

Yeah... this is what i am looking for. Great! – user458766 Aug 18 '15 at 07:04
Why not `i = List[0]` instead of hardcoding `1` to work for any sublist? – Padraic Cunningham Aug 18 '15 at 07:06
@PadraicCunningham: If I understand correctly, the expected output might be `1`, if `1` is not in the list. With `i = List[0]` you'd miss that on a list like, e.g., `[2, 3, 5]`. – Falko Aug 18 '15 at 07:08
You might be right based on the edit, if that is the case the question is a lot simpler – Padraic Cunningham Aug 18 '15 at 07:16

Padraic Cunningham · Answer 2 · 2015-08-18T08:00:23.053

If the sublists are already sorted like you input, just compare the previous to the current element, if the prev +1 is not equal to the current ele add prev + 1 to the output list:

List = [[1, 2, 4, 5], [1, 2, 3, 4, 5, 7], [1, 4, 5, 6]]
out = []
for sub in List:
    prev = sub[0]
    for  ele in sub[1:]:
        if prev + 1 != ele:
            out.append(prev +1)
            break
        prev = ele
print(out)
[3, 6, 2]

It will work for any sublists that are ordered not just lists starting with 1:

List = [[3, 4, 5,7], [10,13,14,15], [100,101,104,105]]

Output:

[6, 11, 102]

And without slicing:

out = []
for sub in List:
    prev = sub[0]
    i = 0
    for ele in sub:
        if i == 0:
            i += 1
            continue
        if prev + 1 != ele:
            out.append(prev +1)
            break
        prev = ele
print(out)

If you always want to find the first missing number starting at 1 and can have 0 or negative numbers, only check each ele and increase i if the ele is > 0:

out = []
for sub in Lists:
    i = 1
    for ele in sub:
        if ele > 0:
            if ele != i:
                out.append(i)
                break
            i += 1
print(out)

That means at worst you do a single pass over each sublist as opposed to O(n^2) approach using in

score 0 · Answer 3 · edited May 23 '17 at 11:58

0

Inspired by this answer:

List = [[1,2,4,5],[1,2,3,4,5,7],[1,4,5,6]]
print [sorted(set(range(1,max(l)+2)).difference(l))[0] for l in List]

Output:

[3, 6, 2]

Sure, this approach uses built-in functions. But you can start from here and break it down by replacing forbidden functions by your own implementations.

edited May 23 '17 at 11:58

Community

1
1

answered Aug 18 '15 at 06:50

Falko

17,076
13
60
105

code looking good and thanks, i still thinking about the actual code like writing in c language :) – user458766 Aug 18 '15 at 06:56

How to find the smallest missing numbers from a list without using inbuilt functions or modules

3 Answers3