subrahmanyam pvb

Greenhorn

Posts: 3

Ulf Dittmer

Rancher

Posts: 42970

73

Ryan McGuire

Ranch Hand

Posts: 1113

7

posted 10 years ago

But what do you do at each of those 2n+1 steps? If you have to compare the "current" element against the other 2n elements to see if its twin is also present, then your algorithm is O(n^2).

Let's say the array has...

5,9,2,4,0,9,8,1,7,8,4,3,2,0,5,6,6,7,1

When you look at the first element (the 5), how do you know whether there's another in the array or not?

Originally posted by Ulf Dittmer:

'2n+1' is the same order of complexity as 'n', so you could simply loop through the whole array to find that element. Or do you mean 'in n steps'?

But what do you do at each of those 2n+1 steps? If you have to compare the "current" element against the other 2n elements to see if its twin is also present, then your algorithm is O(n^2).

Let's say the array has...

5,9,2,4,0,9,8,1,7,8,4,3,2,0,5,6,6,7,1

When you look at the first element (the 5), how do you know whether there's another in the array or not?

Jim Yingst

Wanderer

Sheriff

Sheriff

Posts: 18671

posted 10 years ago

That's pretty easy to solve with a variety of datastructures that would require O(n) additional memory. HashSet comes to mind - every time you find a value, check if it's in the HashSet. If it is, remove it; if not, add it. When you're done, only one element will remain, the one with no match.

Alternately, an array of M/8 bytes may possibly be more efficient - M would be the maximum range (max - min + 1) of the numbers, as you'd need one bit for every possible value the numbers can have. Every time you find a value in the array, toggle the bit corresponding to that value. When done, scan the array (an O(M) operation) for the one nonzero bit. For full-range java ints, the array would be half a gig, which is maybe a bit prohibitive - but for many applications the range may be much smaller than that. Basically this approach would work best in situations where N is comparable in size to (or larger than) M - meaning the memory required by a HashSet of all values may be prohibitively large compared to the memory required for just one bit for each

For that matter, one could also make a custom hashset-like thing with better performance / memory usage designed to just hold ints (or whatever primitive datatype is appropriate). Lots of different possibilities as we contemplate possible optimizations.

Regardless, a simple HashSet solves the original problem, yes?

Alternately, an array of M/8 bytes may possibly be more efficient - M would be the maximum range (max - min + 1) of the numbers, as you'd need one bit for every possible value the numbers can have. Every time you find a value in the array, toggle the bit corresponding to that value. When done, scan the array (an O(M) operation) for the one nonzero bit. For full-range java ints, the array would be half a gig, which is maybe a bit prohibitive - but for many applications the range may be much smaller than that. Basically this approach would work best in situations where N is comparable in size to (or larger than) M - meaning the memory required by a HashSet of all values may be prohibitively large compared to the memory required for just one bit for each

*possible*value. I think the HashSet would be a better option in general, but in some regimes, this latter approach may be superior.For that matter, one could also make a custom hashset-like thing with better performance / memory usage designed to just hold ints (or whatever primitive datatype is appropriate). Lots of different possibilities as we contemplate possible optimizations.

Regardless, a simple HashSet solves the original problem, yes?

"I'm not back." - Bill Harding, *Twister*

Rajasekar Elango

Ranch Hand

Posts: 105

Jim Yingst

Wanderer

Sheriff

Sheriff

Posts: 18671

posted 10 years ago

Raja, I think you're assuming that the array contains two 1's, two 2's, etc. up to two n's, plus an addtional unpaired ("odd") number. That's an unstated assumption. What if the array is { 10, 10, 11 }? Here n = 1, the sum of all elements is 31, and your formula tells us the "odd number" is 29.

"I'm not back." - Bill Harding, *Twister*

Ryan McGuire

Ranch Hand

Posts: 1113

7

posted 10 years ago

I bet if you were told that the problem could be solved in O(n) time using

Let's say each array element could be a full-range Java int. You can find the odd element out with just one int for an array index and

Originally posted by Jim Yingst:

Alternately, an array of M/8 bytes may possibly be more efficient - M would be the maximum range (max - min + 1) of the numbers, as you'd need one bit for every possible value the numbers can have. ... For full-range java ints, the array would be half a gig, which is maybe a bit prohibitive...

I bet if you were told that the problem could be solved in O(n) time using

*considerably*less memory, it might just give away what "the answer" is.

Let's say each array element could be a full-range Java int. You can find the odd element out with just one int for an array index and

*one*int for an "accumulator".

Jim Yingst

Wanderer

Sheriff

Sheriff

Posts: 18671

posted 10 years ago

Yep. I suppose you could've masked it a bit more by only saying that the objective was to use minimal memory, or constant (O(1)) memory, or something like that. Oh well.

**[Ryan]: I bet if you were told that the problem could be solved in O(n) time using considerably less memory, it might just give away what "the answer" is.**

Yep. I suppose you could've masked it a bit more by only saying that the objective was to use minimal memory, or constant (O(1)) memory, or something like that. Oh well.

"I'm not back." - Bill Harding, *Twister*

Joni Salonen

Ranch Hand

Posts: 53

Ryan McGuire

Ranch Hand

Posts: 1113

7

posted 10 years ago

Are we really able to XOR the Strings also... I haven't heard anywhere since....

Ryan. Could you come up how to XOR Strings...

Originally posted by Ryan McGuire:

Heck, even if they were Strings, you could still XOR them all together.

Are we really able to XOR the Strings also... I haven't heard anywhere since....

Ryan. Could you come up how to XOR Strings...

The Best way to predict your future is to create it - Every great individual common man

Ryan McGuire

Ranch Hand

Posts: 1113

7

posted 10 years ago

Can you really

How about this quick-and-dirty code:

(I'm sure there'a a more efficient way to do XORStrings(), but I just wanted to crank out a quick proof-of-concept.)

[ September 22, 2006: Message edited by: Ryan McGuire ]

Originally posted by Ankur Sharma:

Are we really able to XOR the Strings also... I haven't heard anywhere since....

Ryan. Could you come up how to XOR Strings...

Can you really

*not*figure out how to apply XOR to Strings?

How about this quick-and-dirty code:

(I'm sure there'a a more efficient way to do XORStrings(), but I just wanted to crank out a quick proof-of-concept.)

[ September 22, 2006: Message edited by: Ryan McGuire ]