• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

you'll love solving this....

 
subrahmanyam pvb
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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' ???
 
Ulf Dittmer
Rancher
Posts: 42968
73
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
'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'?
 
Ryan McGuire
Ranch Hand
Posts: 1081
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 18671
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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?
 
Rajasekar Elango
Ranch Hand
Posts: 105
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
Jim Yingst
Wanderer
Sheriff
Posts: 18671
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 1081
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 18671
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
[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
Posts: 53
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
What are the elements of the array?

If they are integers, you can simply XOR all of them together.
 
Ryan McGuire
Ranch Hand
Posts: 1081
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Heck, even if they were Strings, you could still XOR them all together.
 
Shaan Shar
Ranch Hand
Posts: 1249
Java Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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...
 
Ryan McGuire
Ranch Hand
Posts: 1081
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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 ]
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic