So I got such exercise:
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.
and how divide number by 7 using bitwise, how to divide by 8 i know it only takes shift to left by 3 i.e. number << 3, but how divide by 7?
The first problem is easy
I'll give you the code for it :)
#include <iostream>
#include <cstdlib>
int main()
{
int A[1000];
// for loop to fill the array with random elements between 1 to 1000
for( int i = 0; i < 1000; i++)
{
A[i] = 1 + rand() %1000;
}
// for loop to find the duplicate integer
for( int j = 0; j < 1000; j++ )
{
if( A[j] == A[j])
cout << "the duplicate integer found " << A[j];
}
return 0;
} // end mainThat doesn't make sense, because A[j] == A[j] you are comparing same values, so they always will be equal...
The first problem is easy
I'll give you the code for it :)#include <iostream> #include <cstdlib> int main() { int A[1000]; // for loop to fill the array with random elements between 1 to 1000 for( int i = 0; i < 1000; i++) { A[i] = 1 + rand() %1000; } // for loop to find the duplicate integer for( int j = 0; j < 1000; j++ ) { if( A[j] == A[j]) cout << "the duplicate integer found " << A[j]; } return 0; } // end main
can you use std::sort(A, A+1000)
and if A[j] == A[j+1] cout << A[j]
Well that might be solution, but i'm not sure. Maybe there is some way without sorting ?
And i made mistake, i was wondering how to multiply number by 7 not divide.
can you use std::sort(A, A+1000)
and if A[j] == A[j+1] cout << A[j]
And i made mistake, i was wondering how to multiply number by 7 not divide.
int x = 21;
x = (x << 2) + (x << 1) + x; //multiply number by 7
cout << x;I'm really distracted today, there was mentioned that i can't use addition or subtraction
int x = 21; x = (x << 2) + (x << 1) + x; //multiply number by 7 cout << x;
First question is interesting one, I researched on it, but the below mentioned link has figured out some really good stuff regarding your first question.
http://aperiodic.net/phil/archives/Geekery/find-duplicate-elements.html.
will try your 2nd question tomorrow :).
how to sum numbers...
it was hard to write this :/
EDIT: small fix
#include <iostream>
using namespace std;
int sum_numbers(int x, int y) {
while(y = (x&y) << ((x ^= y)?1:1));
return x;
}
int main() {
int x = 24;
int y = 3;
for(;y < 100;++y)
cout << sum_numbers(x, y) << '-';
return 0;
}and here is the file code for multiply number by 7
#include <iostream>
using namespace std;
int sum_numbers(int x, int y) {
while(y = (x&y) << ((x ^= y)?1:1));
return x;
}
int multiply_by_seven(int x){
return sum_numbers(sum_numbers((x << 2), (x << 1)), x);
}
int main() {
for (int i = 0; i <= 100; ++i){
cout << multiply_by_seven(i) << endl;
}
return 0;
}
For the array problem:
Without using an intermediary array of some kind (via recursion or on a stack or whatever) the only other way I can think to do it is with math.
You'll need a bignum library, and a list of the first N prime numbers (where N is 1 << bits_per_element).
Start with a temporary bignum with value zero. For each element, add the eth prime number (where e == bitvalue of element) to the temporary.
Now decompose the temporary and determine which prime(s) is(are) composited more than once.
;-)
If it wouldn't be too hard could you explain what exactly this line does while(y = (x&y) << ((x ^= y)?1:1)); ?
how to sum numbers...
it was hard to write this :/
EDIT: small fix#include <iostream> using namespace std; int sum_numbers(int x, int y) { while(y = (x&y) << ((x ^= y)?1:1)); return x; } int main() { int x = 24; int y = 3; for(;y < 100;++y) cout << sum_numbers(x, y) << '-'; return 0; }
i can't explain... but i can wright it like this:
int sum_numbers(int x, int y) {
int sum = x;
int tmp;
do {
tmp = y;
y = (sum&y) << 1;
sum ^= tmp;
} while (y);
return sum;
}this is algorithm and i don't know why it work, but it work :)
So I got such exercise:
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.
If there's 1001 elements, or if the numbers are of the set {1..999} then this is simply solved using the bitwise exclusive-or operator on all the array elements together, and on all the numbers in the set (1..1000 or 1..999, depending on question). The result would be the duplicate number.
As the question stands currently, the method would get the duplicate number xor'd with the missing number (the number from the set not present in the array) - and I cannot think of how to separate them...
Any chance the question is slightly different? (usually if I can't find an answer I just change the question :-)
The sort method suggested is not allowed as it accesses the array elements multiple times.
I doubt that the addition of primes is allowed, as it is essentially just making a copy of the array. From my understanding, the following would perform the same function as addition of primes (or any orthogonal values for that matter):
int_with_n_bits<1000> sum(0); // 1000 bit integer
for(int i = 0; i < 1000; i++){
int v = array[i];
if(sum & 1<<(v-1)) // check if it's already stored
cout << "found duplicate " << v << endl;
sum |= 1<<(v-1);
}As can be seen, the summation is merely converting from the array of values to an array of bits (or array of primes)
Bits != Primes.
No matter what you do you must keep information about all items in the array at once. XOR does that by counting the number of times a bit is toggled. Your array is in the loop. If you want to argue code == data then all arguments fail by default.
For the constricted case given of 999 values out of a choice of 1000 then XOR works fine... Primes will always work because of the fundamental theorem of arithmetic.
The original problem states that it is OK to use other variables and not arrays. An atomic number is not an array.
Hope this helps.
Here's the important segment of the array duplicates problem:
for(int i = 0; i < 1000; i++)
{
for(int j = 0; j < 1000; j++)
{
if(i != j)
{
if(arr[i] == arr[j])
{
return arr[i];
}
}
}
}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.
Actually, I came back to re-edit my post. The first time I said that XOR wouldn't work, but I wasn't sure and didn't want to think about it, so I edited it to give you the benefit of the doubt (that is, assuming that you thought about it).
I was outside reading and it just passed through my brain that XOR can't work, because choosing 999 elements out of 1000 possibilities 1000 times means at least one duplicate. Stipulating only one duplicate, then XOR cannot work because the result will indicate two numbers: the duplicate and the one that was not chosen. Since you don't know which is which, it cannot work. (In fact, you can't even tell which two numbers are indicated!)
The solution you just posted accesses each element of the array N times, where the array is N items long. The OP specified that each element can be accessed only once... meaning O(N), but yours is O(N^2). Oops.
Wow, those were some pretty ridiculous algorithms you guys came up with.
Well, if you want to avoid making friends, you might have succeeded. Considering your algorithm ignores every requirement of the problem, it seems me blithely arrogant to call other attempts "ridiculous". Prove a superior solution first.
And learn some math.
I also know that "primes" != "bits"! (they're spelt differently for a start). I must admit that I don't really understand how your primes method works (I almost thought I had an idea before - so sorry for writing off your answer). I assumed you were using primes so that you could store away all the elements in an orthogonal way (which is what the method of bits is doing - using an array of bits instead of an array of ints).
Tell me Duoas, can you recreate the original array from the sum of primes?
choosing 999 elements out of 1000 possibilities 1000 times means at least one duplicate. Stipulating only one duplicate, then XOR cannot work because the result will indicate two numbers: the duplicate and the one that was not chosen.
I already stated that in my original post, which is why I asked if there was a small typo in the question.
The XOR method will work, given the constraints I stated (i.e. choosing 999 out of 999 possibilities, and duplicating one of them). Code below:
// note array contains numbers >0 and <1000 - there is a single duplicate
int findDup(int array[1000]){
int xorVal = 0;
for(int i = 0; i < 1000; i++)
xorVal ^= arr[i]; // access array elements only once
// now xorVal contains the exclusive-or of all non-duplicated elements in the array once; and the duplicated element twice (x ^ x == 0)
// find who's missing:
for(int i = 0; i < 999; i++)
xorVal ^= (i+1); // xor with all the expected (i.e. no dups) numbers that could be in array
// now xorVal contains the exclusive-or of all non-duplicated elements in the array twice (a ^ a == 0); and the duplicated element three times (x ^ x ^ x == x)
return xorVal;
}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. So:
Yes: if element order is not important.
No: if element order is important.
Click on "fundamental theorem of arithmetic" in post #11.
You should be aware, though, that using primes is far more expensive than just using a temporary array would be... prohibitively so for large arrays. This kind of question is usually an algorithms thought experiment. Knowing something can be done doesn't necessarily mean it should be done. In this case, the restrictions on the algorithm's data structures are unrealistic (usually). But being restricted to one pass over the array itself is not.
Hope this helps.
[edit] I haven't looked over the original post since my first reply. I was only responding to subsequent posts. If you are restricted to using all given numbers and duplicating only one, then XOR will work perfectly. ;)
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.
> 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. :-O :-/ :)
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:
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.
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:
result = 0
for each x in xs:
result = result XOR xresult = 1
for each x in xs:
result = result * nth_prime( x )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:
for n = 1 to N:
ns = ns:n
result = result XOR n
ns = ns:resultfor n = 1 to N
while result MOD nth_prime( n ) == 0:
ns = ns:n
result = result DIV nth_prime( n )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.
Listen, don't get all hot under the collar. I have not said anything offensive to you.
Don't worry about me, I hadn't got even the slightest bit offended. My use of exclaimation points '!', and even double-exclaimation points was to emphasis a sentence; not to be read as exhasperation/anger/etc.
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.
It can only 'count' # of bit toggles to 1 (and back), i.e. modulus 2, information is lost & not stored.
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!
i can't explain... but i can wright it like this:
int sum_numbers(int x, int y) { int sum = x; int tmp; do { tmp = y; y = (sum&y) << 1; sum ^= tmp; } while (y); return sum; }this is algorithm and i don't know why it work, but it work :)
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
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.
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. [B]You can access each array member only once[/B], 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.
Thanks to you all for your time and replies.
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.
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
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.