•
•
•
•
What is DaniWeb IT Discussion Community?
You're currently browsing the C++ section within the Software Development category of DaniWeb, a massive community of 391,610 software developers, web developers, Internet marketers, and tech gurus who are all enthusiastic about making contacts, networking, and learning from each other. In fact, there are 2,613 IT professionals currently interacting right now! Registration is free, only takes a minute and lets you enjoy all of the interactive features of the site.
Please support our C++ advertiser:
Views: 1157 | Replies: 37
 |
•
•
Join Date: Jun 2007
Posts: 179
Reputation: 
Rep Power: 2
Solved Threads: 29
Junior Poster
•
•
•
•
Originally Posted by Duoas 
Well, you can get all the original numbers back, including all duplicates, triplicates, etc, but you cannot get the original order of the elements back.
This is making a (sorted) copy (yes you lose order information) of the array, which in my opinion (which you may choose to ignore) is disallowed by the statement that the array may not be copied.
I'm going to be quiet now, as I've added nothing constructive to the OPs original stated question.
Last edited by dougy83 : Jul 5th, 2008 at 7:23 pm.
•
•
Join Date: Oct 2007
Location: Cherry Hill, NJ
Posts: 1,809
Reputation: 
Rep Power: 11
Solved Threads: 184
> This is making a (sorted) copy ... of the array
Yes, that is correct. The same is true of the XOR method. The problem cannot be solved unless you are permitted to have state. That is a fundamental concept in Turing machines.
The original problem indicated that you may have one or more (presumably a lot fewer than values in the array) temporary variables, but you may not create another array. So could I use a linked list? I think the intent of the question is that you must solve the problem without creating another list of values.
A number is not a list of any kind. (Though it can be represented as a list of digits. Or prime factorizations.)
If you really want to be technical, numbers don't exist.
Yes, that is correct. The same is true of the XOR method. The problem cannot be solved unless you are permitted to have state. That is a fundamental concept in Turing machines.
The original problem indicated that you may have one or more (presumably a lot fewer than values in the array) temporary variables, but you may not create another array. So could I use a linked list? I think the intent of the question is that you must solve the problem without creating another list of values.
A number is not a list of any kind. (Though it can be represented as a list of digits. Or prime factorizations.)
If you really want to be technical, numbers don't exist.
Last edited by Duoas : Jul 5th, 2008 at 8:47 pm.
•
•
Join Date: Jun 2007
Posts: 179
Reputation:
Rep Power: 2
Solved Threads: 29
Junior Poster
I know I said I'd be quiet... but...
Who ever said numbers don't exist? Maybe not imaginary ones, but surely real numbers exist.
From what wikipedia told me about Turing machines, they are not revelvant to this discussion whatsoever.
The XOR method does not make a copy of the array!! You cannot retrieve more than one value from it, ever! (not without knowledge of all the input data (except the data we want to retrieve), - it stores only 1 value)
Using a huge number to contain the sum of N orthogonol/separable values is akin to having N separate numbers.
in the case:
using magicNumber (which you can - and will - argue is a single number), as I see it, is making use of a copy of the array. Even if you translate the array by e.g. rearranging the elements, multiplying by primes, etc., so long as there are N separable components in the number, then you've just made a copy (albeit a fancy copy) of the original.
Who ever said numbers don't exist? Maybe not imaginary ones, but surely real numbers exist.
From what wikipedia told me about Turing machines, they are not revelvant to this discussion whatsoever.
The XOR method does not make a copy of the array!! You cannot retrieve more than one value from it, ever! (not without knowledge of all the input data (except the data we want to retrieve), - it stores only 1 value)
Using a huge number to contain the sum of N orthogonol/separable values is akin to having N separate numbers.
in the case:
int_with_n_bits[32] array[64]; int_with_n_bits[32*64] magicNumber = *(int_with_n_bits[32*64]*)array;
using magicNumber (which you can - and will - argue is a single number), as I see it, is making use of a copy of the array. Even if you translate the array by e.g. rearranging the elements, multiplying by primes, etc., so long as there are N separable components in the number, then you've just made a copy (albeit a fancy copy) of the original.
Last edited by dougy83 : Jul 5th, 2008 at 9:18 pm.
•
•
Join Date: Oct 2007
Location: Cherry Hill, NJ
Posts: 1,809
Reputation:
Rep Power: 11
Solved Threads: 184
Listen, don't get all hot under the collar. I have not said anything offensive to you.
numbers
Show me a "two".
You can show me two of something, but two, by itself, does not exist. It is an abstract concept -- a way of thinking about real, extant things.
turing
After you've spent as many years as I have dealing with computational theory you can lecture me on the relevance of Turing machines. Whatever it is you got out of the Wikipedia article (and I commend you for going there), the solvability of these kinds of questions at the very heart of Church and Turing's conjecture.
If a problem is not representable by a (universal) Turing machine, it cannot be solved. Meaning that, if you want to remove state from the program, you have essentially made it unsolvable.
In plainer English: if you are not allowed to remember all the values in the array (up to and including the value currently being examined), you simply cannot tell me whether a given value is a repeat of a former one. There is no way around that.
copies
Conceptually, the XOR method makes a copy of the array the exact same way the prime numbers method does. Both result in a single number. Both can be used to reproduce the original array [1]. The way they achieve that goal is different, and the feasibility of the XOR method is conditional on the input restrictions, but in both cases a single number is modified in a separable way to track what values are or are not in the array.
With XOR, it is by counting the number of times each bit in the binary number is toggled.
With prime numbers, it is by using the fundamental theorem of arithmetic [2], which counts the number of times a prime factor is multiplied into a composite number.
Either way, you are tracking N separate numbers!
magic numbers
And frankly, I wish you would stop arguing that I think a single number cannot be used as a copy of an array. I have already stated multiple times that that is the point. It is a fancy copy of the array.
The only thing magical about it is its relationship to what people don't know. I've got an awful lot of math under my belt. And I know plenty of people who could blow me out of the water. It is time to swallow your pride and learn something, before your foot gets too deep down your throat.
It is mighty uncomfortable there. Believe me I know!
Whew. I've spent a good amount of time formatting this article for readability. I hope you find it useful.
footnotes
[1] To build the number:
You may have noticed by now that the way the result is built looks an awful lot alike in both methods.
To extract the original array, in sorted order:
The XOR algorithm has an extra line because we don't know what the duplicate number is until we have removed all other numbers from result. (So the duplicate number is out of order in the reproduced array.)
But in either case, ns now has the same list of numbers as xs does, though maybe not in the same order.
[2] Which I wish you would spend some time reading. This is the third time I've referenced the article. The FT of A is fundamental to understanding arithmetic, and consequently, my algorithm, and its relationship to the XOR algorithm.
Hope this helps.
numbers
Show me a "two".
You can show me two of something, but two, by itself, does not exist. It is an abstract concept -- a way of thinking about real, extant things.
turing
After you've spent as many years as I have dealing with computational theory you can lecture me on the relevance of Turing machines. Whatever it is you got out of the Wikipedia article (and I commend you for going there), the solvability of these kinds of questions at the very heart of Church and Turing's conjecture.
If a problem is not representable by a (universal) Turing machine, it cannot be solved. Meaning that, if you want to remove state from the program, you have essentially made it unsolvable.
In plainer English: if you are not allowed to remember all the values in the array (up to and including the value currently being examined), you simply cannot tell me whether a given value is a repeat of a former one. There is no way around that.
copies
Conceptually, the XOR method makes a copy of the array the exact same way the prime numbers method does. Both result in a single number. Both can be used to reproduce the original array [1]. The way they achieve that goal is different, and the feasibility of the XOR method is conditional on the input restrictions, but in both cases a single number is modified in a separable way to track what values are or are not in the array.
With XOR, it is by counting the number of times each bit in the binary number is toggled.
With prime numbers, it is by using the fundamental theorem of arithmetic [2], which counts the number of times a prime factor is multiplied into a composite number.
Either way, you are tracking N separate numbers!
magic numbers
And frankly, I wish you would stop arguing that I think a single number cannot be used as a copy of an array. I have already stated multiple times that that is the point. It is a fancy copy of the array.
The only thing magical about it is its relationship to what people don't know. I've got an awful lot of math under my belt. And I know plenty of people who could blow me out of the water. It is time to swallow your pride and learn something, before your foot gets too deep down your throat.
It is mighty uncomfortable there. Believe me I know!
Whew. I've spent a good amount of time formatting this article for readability. I hope you find it useful.
footnotes
[1] To build the number:
XOR Syntax (Toggle Plain Text)
Primes Syntax (Toggle Plain Text)
To extract the original array, in sorted order:
XOR Syntax (Toggle Plain Text)
Primes Syntax (Toggle Plain Text)
But in either case, ns now has the same list of numbers as xs does, though maybe not in the same order.
[2] Which I wish you would spend some time reading. This is the third time I've referenced the article. The FT of A is fundamental to understanding arithmetic, and consequently, my algorithm, and its relationship to the XOR algorithm.
Hope this helps.
Last edited by Duoas : Jul 5th, 2008 at 10:24 pm.
•
•
Join Date: Jun 2007
Posts: 179
Reputation:
Rep Power: 2
Solved Threads: 29
Junior Poster
•
•
•
•
Originally Posted by Duoas
Listen, don't get all hot under the collar. I have not said anything offensive to you.
I still have issues with the concepts you have written of, but I do not wish for further 'convincing'. In my mind still, the only reason the XOR method works for the constrained input vector is that all the expected numbers (no dups) are already known (1..n) - the only thing we don't know is the dup num which is mixed in with the stew, and once we remove all traces of the known bits, the dup num is left; there is nothing seperable without knowing all other constituents.
•
•
•
•
With XOR, it is by counting the number of times each bit in the binary number is toggled.
OK, I might read [2] later, at first glance it appears to state that any number has a unique set of irreducable/prime factors - I learnt that in grade 8 (not the proofs obviously). I fail to see the relevance of that to any of my statements either ([2] is relevant to your solution; not to my ramblings).
I may have said some off hand comments that have been taken to heart (e.g. that real numbers must be real), but on the whole I'm not trying to annoy you.
Anyway, this is definately my last note in this thread on the topic (abuse is always welcome via the PM service). I seem to be responsible for the hijack of this thread. Good luck to the OP finding a solution!
•
•
Join Date: Mar 2005
Location: Phnom Penh, Cambodia
Posts: 393
Reputation:
Rep Power: 5
Solved Threads: 34
Posting Whiz
•
•
•
•
Originally Posted by ivailosp
i can't explain... but i can wright it like this:
this is algorithm and i don't know why it work, but it workcpp Syntax (Toggle Plain Text)
This algorithm is very easy to understand if you have read this link.
For example: I have number 11 and 7. I want sum those two numbers by using binary arithmetic.
11 : 1 0 1 1 07 : 0 1 1 1 + ---------------------
Rule
- 0 + 0 = 0
- 0 + 1 = 1
- 1 + 0 = 1
- 1 + 1 = 0 carry 1
1 1 1 1 (carried digits)
11 : 1 0 1 1
07 : 0 1 1 1 +
---------------------So,
y = (sum&y) << 1; is a carrier and we use XOR operator in this code sum ^= tmp; because it fulfil the rule of binary addition arithmetic. Last edited by invisal : Jul 6th, 2008 at 1:43 am.
Yesterday is a history, tomorrow is a mystery, today is a gift.
Behind every smile is a tear.
Visal .In
Behind every smile is a tear.
Visal .In
•
•
Join Date: Mar 2005
Location: Phnom Penh, Cambodia
Posts: 393
Reputation:
Rep Power: 5
Solved Threads: 34
Posting Whiz
•
•
•
•
Originally Posted by death_oclock
This just checks every element of the array against every other element of the array.
Wow, those were some pretty ridiculous algorithms you guys came up with.
Did you read the poster problem?
You have array of 1000 elements they all are random numbers from 1 to 1000 and there is only one duplicate number. You can access each array member only once, can you find duplicate value? And you can't create another array. You can create some variables to store temporary data.
In your code, you have access 999 times for each array member.
Last edited by invisal : Jul 6th, 2008 at 1:48 am.
Yesterday is a history, tomorrow is a mystery, today is a gift.
Behind every smile is a tear.
Visal .In
Behind every smile is a tear.
Visal .In
•
•
Join Date: Jul 2008
Posts: 6
Reputation:
Rep Power: 0
Solved Threads: 0
Newbie Poster
Thanks to you all for your time and replies.
•
•
Join Date: Oct 2007
Location: Cherry Hill, NJ
Posts: 1,809
Reputation:
Rep Power: 11
Solved Threads: 184
We're glad to have been helpful (if indeed you found the thread enlightening...)
@dougy83
You are correct about how XOR works. You must have knowledge not encoded in the number to untangle it.
And I don't think it is hijack to explore the OP's questions... so don't worry about it -- No abuse headed your way from me.
@dougy83
You are correct about how XOR works. You must have knowledge not encoded in the number to untangle it.
And I don't think it is hijack to explore the OP's questions... so don't worry about it -- No abuse headed your way from me.
•
•
Join Date: May 2008
Location: Infinite Castle, below Beltline
Posts: 279
Reputation:
Rep Power: 1
Solved Threads: 22
Posting Whiz in Training
Considering the first problem, You guys have come up with brilliant answers which is taking me more than 20 minutes to understand. Did not someone gave a link to an easier answer so that a novice like me could understand.
Add all the element in the array subtract 1000 * 1001 / 2. The answer is the duplicate. Hope I am right
Add all the element in the array subtract 1000 * 1001 / 2. The answer is the duplicate. Hope I am right
|
•
•
•
•
Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
•
•
•
•
•
•
•
•
DaniWeb C++ Marketplace
Linear Mode
Similar Threads
- Bitwise: Convert Primitives (Java)
- hex string to true binary w. bit manipulation (Java)
- I Need Help (C++)
- Adding mouse listener to a frame (Java)
- help with errors (C++)
Other Threads in the C++ Forum
- Previous Thread: Converting std::string to System::String^ NEED HELP
- Next Thread: Exception in Visual C++
