[myselfandi]

We have an array of C strings, each string appears twice except for one string appears once.

You need to write an algorithm that return the one string that appears once. Write an algorithm that solve this in O(n).

I'll post the solution in one day.

[Securifier]

You want each string in the array only appears once?
Soooo EZZZ :)

[YouthInAsia]

So what's the challenge....

[myselfandi]

You want each string in the array only appears once?
Soooo EZZZ :)

Sorry edited, No return the string in the array that appears once.

---

So what's the challenge....

Edited

[Hoodie+]

I remember a problem like this in college.
I solved it like this by creating a hash of the current element i am checking and seeing if it is in a list of hashes, if it is I would delete it from the list and if it isn't I would add it to the hash list.
Not sure if it is fast/effective but it was working well.

[myselfandi]

I remember a problem like this in college.
I solved it like this by creating a hash of the current element i am checking and seeing if it is in a list of hashes, if it is I would delete it from the list and if it isn't I would add it to the hash list.
Not sure if it is fast/effective but it was working well.

you are right, Hashing is a good way to solve the problem, traversing all array elements and putting them in a hash table, then can use the array elements as a key and for each occurrence you increment the value by 1. now you simply you can traverse the array and print the element with value 1 in the hash table. though this method require extra space. there is another way of solving this problem that uses O(1).

[6577657534735]

you are right, Hashing is a good way to solve the problem, traversing all array elements and putting them in a hash table, then can use the array elements as a key and for each occurrence you increment the value by 1. now you simply you can traverse the array and print the element with value 1 in the hash table. though this method require extra space. there is another way of solving this problem that uses O(1).

xor every element of the array together, the result is the string that occurs once. same can be said of any data structure that can be represented as a byte array

the reason is if you xor a byte by itself is cancels out to 0, so if you xor every string twice they cancel out, and the one you only xor'd once is xor'd by 0, so it appears in the result

if anyone else wants more classic programming puzzles and interview questions like this, read Cracking The Code Interview

[myselfandi]

xor every element of the array together, the result is the string that occurs once. same can be said of any data structure that can be represented as a byte array

the reason is if you xor a byte by itself is cancels out to 0, so if you xor every string twice they cancel out, and the one you only xor'd once is xor'd by 0, so it appears in the result

if anyone else wants more classic programming puzzles and interview questions like this, read Cracking The Code Interview

👍 👍

[Hoodie+]

xor every element of the array together, the result is the string that occurs once. same can be said of any data structure that can be represented as a byte array

the reason is if you xor a byte by itself is cancels out to 0, so if you xor every string twice they cancel out, and the one you only xor'd once is xor'd by 0, so it appears in the result

if anyone else wants more classic programming puzzles and interview questions like this, read Cracking The Code Interview

I don't believe I understand this way. Could you clarify it more?
I understand the fact that if you xor two equal strings that they will cancel out.

[myselfandi]

I don't believe I understand this way. Could you clarify it more?
I understand the fact that if you xor two equal strings that they will cancel out.

XOR is commutative so a if have this array {5,4,7,5,4}, and then xor all the element in it, the result will be 7
because 5^4^7^5^4 => 5^5 ^ 4^4 ^ 7 => 0^0 ^ 7 => 7

[Hoodie+]

XOR is commutative so a if have this array {5,4,7,5,4}, and then xor all the element in it, the result will be 7
because 5^4^7^5^4 => 5^5 ^ 4^4 ^ 7 => 0^0 ^ 7 => 7

Alright but how does that help us here?

[6577657534735]

Alright but how does that help us here?

we have a set of strings, every string in the set appears twice except one. we want to find the string that appears once. we can use a hash table to count the number of instances of each string and find the one whose value is one, but this requires O(n) space to store this info in the hash table. instead we want to decrease it to O(1) space, as in space not related to the number of strings you're comparing. for this reason we can xor together every string, and the ones that appear twice cancel out, becoming 0, then the string that appears once is xor'd with 0, resulting in itself. thus if you xor every string in the set, the result is the string that appears once, requiring only O(1) space on the number of strings in the set, and in fact this is the fastest method too since xor is wayy faster than hash tables

[YouthInAsia]

Code

arrayofstrings = {"hello","world","boost","start","world","boost","hello"}//start
for(index = 1 ; index < lengthofarrayofstrings; ++index)
    onlyone = arrayofstrings[index-1] ^ arrayofstrings[index]
print(onlyone)//start