Re: Algorithm to find break in contiguity
- From: "mensanator@xxxxxxx" <mensanator@xxxxxxx>
- Date: 25 Jan 2007 10:39:05 -0800
On Jan 25, 12:17 pm, "mensana...@xxxxxxx" <mensana...@xxxxxxx> wrote:
use...@xxxxxxxxxxxxxxx wrote:
I need an efficient algorithm for the following problem:
If you have unique N-1 numbers in the range 1 to N, find the missing
number.
Of course if you could generalize that to finding missing k numbers
from a sample of N-k unique numbers that are in the range 1 to N that
would be better.
Thanks,import random
Bhta# Python
# build a list of N consecutive numbers
N = 100
n = range(N)
# now remove some random quantity of random elements
for q in xrange(random.randint(5,27)):
m = random.randint(0,len(n)-1)
n.pop(m)
missing_numbers = []
for i in xrange(len(n[:-1])): # walk through the list
if (n[i+1]-n[i]) != 1: # a gap >1 implies missing
p = n[i]+1
while p<n[i+1]: # allow for consecutive missing
missing_numbers.append(p)
p += 1
print 'The list:'
print n
print 'The missing numbers:'
print missing_numbers
## The list:
## [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13,
## 14, 16, 17, 18, 19, 21, 22, 23, 24, 25, 27, 28,
## 29, 30, 31, 32, 33, 34, 35, 37, 43, 44, 46, 47,
## 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 59, 61,
## 62, 63, 64, 65, 66, 67, 68, 69, 70, 73, 76, 77,
## 78, 79, 80, 81, 82, 84, 85, 86, 89, 90, 91, 92,
## 94, 95, 96, 97]
##
## The missing numbers:
## [15, 20, 26, 36, 38, 39, 40, 41, 42, 45, 58, 60,
## 71, 72, 74, 75, 83, 87, 88, 93]
Checking for boundary conditions would help.
.
- Prev by Date: ANNOUNCE: TclTalk - A Tcl/Tk runtime and development environment based on TclKit
- Next by Date: Re: Algorithm: walking around a circle
- Previous by thread: ANNOUNCE: TclTalk - A Tcl/Tk runtime and development environment based on TclKit
- Next by thread: Re: Algorithm to find break in contiguity
- Index(es):
Relevant Pages
|
