aspose file tools*
The moose likes Programming Diversions and the fly likes you'll love solving this.... Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Spring in Action this week in the Spring forum!
JavaRanch » Java Forums » Other » Programming Diversions
Bookmark "you Watch "you New topic
Author

you'll love solving this....

subrahmanyam pvb
Greenhorn

Joined: Jan 02, 2006
Posts: 3
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' ???


balu------->>U.
Ulf Dittmer
Marshal

Joined: Mar 22, 2005
Posts: 42285
    
  64
'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'?


Ping & DNS - my free Android networking tools app
Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 1010
    
    3
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

Joined: Jan 30, 2000
Posts: 18671
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?


"I'm not back." - Bill Harding, Twister
Rajasekar Elango
Ranch Hand

Joined: Sep 13, 2004
Posts: 105
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
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: 1010
    
    3
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
[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.
Joni Salonen
Ranch Hand

Joined: Jan 07, 2006
Posts: 53
What are the elements of the array?

If they are integers, you can simply XOR all of them together.
Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 1010
    
    3
Heck, even if they were Strings, you could still XOR them all together.
Shaan Shar
Ranch Hand

Joined: Dec 27, 2005
Posts: 1249

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: 1010
    
    3
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 ]
 
It is sorta covered in the JavaRanch Style Guide.
 
subject: you'll love solving this....