need help defining Constant memory requirement

[Tim Peters]

[Jani Yusef]
> I have a HW problem stated as shown at the top of the solution. The
> thing is is that I am not 100% sure wtf constant memory means.

It means the amount of memory needed is independent of input size.

> Well, I think I do but I am confused. Does my solution use contant
> memory in terms of the length of the list i?

The "constant" in "constant memory" means you don't get to use more
memory for larger inputs, so "in terms of the length of the list"
isn't valid.  Your solution requires creating a dict with n-1
elements, and so requires O(n) memory, not constant memory.

> If so why not

Because the amount of memory needed increases as the input size increases.

> and how could I change it to be so?

With the approach you've taken, you cannot.  You need a different
approach.  Since finding such an approach is apparently the point of
the exercise, I'm not going to spell that out.  As a hint, you need to
*exploit* all the information you've been given about the inputs. 
Note that the solution you have works for any input sequence, whether
or not the values range from 1 to n-1, and whether there are 0, 1, 2,
..., or millions of duplicates.  You only *need* a solution that works
in the case of an input sequence containing a permutation of 1 .. n-1,
plus exactly one duplicate.

> I am sure the solution is O(n) since the list must only iterated once and the
> dictionary is O(1), correct?

Yes, it's O(n) (expected) in time, but also O(n) in space.

> Thanks for the help!!
> 
> #You are given a sequence S of n numbers whose values range from 1 to n-1.
> #One of these numbers repeats itself once in the sequence.
> #(Examples: {1 2 3 4 5 6 3}, {4 2 1 2 3 6 5}).
> #Write a function that finds this repeating number using a constant
> #amount of memory and linear time.
> import sys
> i=[1,3,4,5,3]

Note that this example doesn't meet the input requirements -- you're
not required to get the right answer for this one.  [1, 3, 4, 2, 3]
meets the requirements, though.

> tally={}
> for a in i:
>        if tally.has_key(a):
>                print "repeated number is "+str(a)
>                sys.exit(0)
>        else:
>                tally[a]=1
> print "no repeat found"

You're not required to get the right answer in the case of no duplicates either.

FYI, it is possible to solve the problem with a constant number of
memory locations, assuming a memory location is big enough to hold one
integer.  That isn't *really* constant-memory either, though, because
holding one integer requires a number of bits proportional to log(n),
which also increases as the input size increases; I suspect your
instructor is overlooking that detail.