This week's book giveaway is in the Servlets forum. We're giving away four copies of Murach's Java Servlets and JSP and have Joel Murach on-line! See this thread for details.

hi all. this might be an old cracker.. but i have recently solved it.

there is an array with 2n+1 elements wherein 'n' elements are repeating twice. there is only one odd element. find that with a complexity in the order of 'n' ???

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?

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 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?

Sum of Elements in array = 2 * Sum of all numbers until n + odd numer

odd number = (sum of all elements in array) - n*(n+1)

Thanks, Raja

SCJP 1.4

Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671

posted

0

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.

Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 1006

3

posted

0

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

Joined: Jan 30, 2000
Posts: 18671

posted

0

[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.

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

Joined: Feb 18, 2005
Posts: 1006

3

posted

0

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 ]