you'll love solving this....
subrahmanyam pvb
Greenhorn
Posts: 3
Ulf Dittmer
Rancher
Posts: 42970
73
Ryan McGuire
Ranch Hand
Posts: 1105
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 fullrange 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 hashsetlike 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 fullrange 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 hashsetlike 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: 1105
7
posted 10 years ago
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 fullrange Java int. You can find the odd element out with just one int for an array index and one int for an "accumulator".
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 fullrange 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 fullrange 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
[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.
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: 1105
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: 1105
7
posted 10 years ago
Can you really not figure out how to apply XOR to Strings?
How about this quickanddirty code:
(I'm sure there'a a more efficient way to do XORStrings(), but I just wanted to crank out a quick proofofconcept.)
[ 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 quickanddirty code:
(I'm sure there'a a more efficient way to do XORStrings(), but I just wanted to crank out a quick proofofconcept.)
[ September 22, 2006: Message edited by: Ryan McGuire ]
You guys wanna see my fabulous new place? Or do you wanna look at this tiny ad?
the new thread boost feature: great for the advertiser and smooth for the coderanch user
https://coderanch.com/t/674455/ThreadBoostfeature
