1

I'm new to python and I need help in trying to find all unused and the first unused/missing number in an array (in python 2.7.3)?

The array is of length 20 and is used by an application. When the application is launched, the array is empty, but as users begin to populate it, I need to find all unused numbers and first unused number.

Think of it as a car-park with 20 spots numbered 1 to 20. As people begin to park their cars, the spaces get filled. People may not necessarily park cars in a sequence, two people may park in spots 1 and 16, so i need to find all the missing spots and the first unused parking spot.

Parking cars is given as an example to help you understand what I'm trying to convey. Array will always be integer, and will hold values from 1 to 20.

Below is what the code should do

On Launch, myArray is empty:

myarray = []

So the first missing number should be 1 (i.e. Park car in first spot)

missingNumbers = [1,2,3,.......20]
firstMissingNoInMyArray = 1

As spaces in the array are filled, the array will look like this

myarray = [1, 5, 15]

So first missing number and missing numbers are: 

missingNumbers = [2,3,4,6,7,8,9,10,11,12,13,14,16,17,18,19,20]. 
firstMissingNoInMyArray = 2

I need to see both missing numbers list and the first missing number, can anyone help with Python code, I'm restricted to using Python 2.7.3; if you have a solution in Python 3, do write it, it may help Python 3 users.

Many thanks in advance.

Improve this question
1
  • what do you mean "see" both missing numbers list and first missing number? are you not able to use a print statement? Or is your question how to generate the missingNumbers and firstMissingNoInMyArray items? Commented Aug 16, 2016 at 14:42

4 Answers 4

Reset to default
2

You can use sets then you can simply subtract the sets. In order to see the first missing number you can take the min in the resulting set:

all_nums = set(xrange(1, 21))
arr = set(xrange(5, 10))

print all_nums - arr 
print min(all_nums - arr) 
# note that sets are unordered
>>   {1, 2, 3, 4, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}
     1

This should work on Python 2.7.3, but you should consider upgrading anyway. Python 2.7.3 is 7 years old.

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

Comments

2

I think this listcomprehension should do the trick for you

missingNumbers = [ i  for i in range(20) if i not in myarray ]

to get the first number you only need to take the first element 

firstMissingNoInMyArray = missingNumbers[0]
Improve this answer

Comments

1

You could use set operations.

limit = 20
myarray = [1, 5, 15]  # Example
missingNumbers = list(set(range(1, limit + 1)) - set(myarray))

print 'Missing numbers ->', missingNumbers
print 'First missing number ->', missingNumbers[0] # Access the first element.

Sample Output:

Missing numbers -> [2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 16, 17, 18, 19, 20] 
First missing number -> 2

Although user @Magellan88's solution is quite pythonic, set operations are highly optimized for this class of calculations. Running some bench marks below, the list comprehension takes significantly longer to finish execution even for smaller data sets -> Search list: 100,000 items, list to subtract -> 100 items.

import timeit
print timeit.timeit("list(set(range(1,100000)) - set(range(1,100)))", number=100)
print timeit.timeit("[ i  for i in range(1,100000) if i not in myarray]", number=100, setup="myarray = range(1,100)")

Results (in seconds):

  • 1.43372607231 - Set operations.
  • 18.2217440605 - List comprehension.

Set difference is a relatively low costing operation with a time complexity of O(n), (python documentation on complexities). Sets in python are essentially implemented using a hash-table giving way to very fast operations (source code).

Meanwhile, in the list comprehension, there is an in operation which has an average case of O(n), this operation occurs within a for loop O(n), thus giving us an average time complexity of O(n2). The list comprehension follows a quadratic asymptotic growth pattern (far slower than the set operation).

Improve this answer

5 Comments

Also a nice solution, and for big Arrays (or better lists) probably quite performant.
Cool, thanks for the benchmarks. Is this factor of two in runtime the same for let's say two orders of magnitude less items?
@Magellan88 Great question! Updated my answer with an explanation! For 1000 iterations, the set operation took 12.9706220627 seconds, while the list comprehension took 176.801266909 seconds.
It's nice to see sets flexing their O(n) muscles in the face of lists' O(n^2) peasantry.
That's a very good answer, now instead of answering I really learned something, thanks!
0

If you know the upper limit of the range, then remove element, that came from user, from pre-populated list and return the first element. Like below:

prepop_list = [ i for i in xrange( 1, 20+1 ) ]

def new_user( item ):
    if item in prepop_list:
        prepop_list.remove( item )
    else:
        return "Item "+ str(item) +" not found"

    return prepop_list[0]

first_e_pos = new_user( 4 ) # some new user reserved 4th position
print( first_e_pos )
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.