Aha! here is the other part:
http://en.wikipedia.org/wiki/Floyd's_cycle-finding_algorithm
On Aug 24, 2:11 am, wbspresslyjr <[EMAIL PROTECTED]> wrote:
> Oops -- for approach 1. down here, I meant to say that the hash table
> breaks the constant space requirement... I guess I got ahead of
> myse
Oops -- for approach 1. down here, I meant to say that the hash table
breaks the constant space requirement... I guess I got ahead of
myself :) (this also applies to sets, and about any other data
structure in general)...
On Aug 24, 1:00 am, wbspresslyjr <[EMAIL PROTECTED]> wrote:
> I've heard
I've heard this problem stated as such: assume you have an array of N
numbers, each ranging on the interval [1,N-1], only one of these
elements repeating in Read-Only memory. You only have O(1) (constant)
"scratch" space to work with, and you need the algorithm to run in
O(n) time.
There were man
Either case is O(n), in fact.
On 8/23/07, ilija <[EMAIL PROTECTED]> wrote:
>
>
> If the subarray needs to be continuous, then you can do it using DP.
> If it doesn't, you can do it using an O(n) algo - simply sum all the
> positive integers.
>
> On 22 kol, 19:55, Ravi <[EMAIL PROTECTED]> wrote:
>
If the subarray needs to be continuous, then you can do it using DP.
If it doesn't, you can do it using an O(n) algo - simply sum all the
positive integers.
On 22 kol, 19:55, Ravi <[EMAIL PROTECTED]> wrote:
> You're given an array containing both positive and negative integers
> and required to f
