Python Forum

Question:
For a given list of numbers, only one digit is repeated odd number of times. Pass the list through function and return the number which is repeated odd number of times.

I have a solution for it. But, I found another solution by other user which I did not understand. Here is the code

def find_it(seq):
    result = 0
    for x in seq:
        result ^= x
    return result

find_it([1,2,3,1,2,3,1])

XOR seems to be implemented but, how is the only odd number being detected.

More explanation:
I have tried printing the binary values of result and x before and after statement result ^= x to understand what is happening but, could not.
Any other resources that you can point me to get better understanding?

 For value 1 , Before ^x Operation. bin(result) =  0b0 , bin(x) =  0b1
 For value 1 , After ^x Operation. bin(result) =  0b1 , bin(x) =  0b1
Result =  1 

 For value 2 , Before ^x Operation. bin(result) =  0b1 , bin(x) =  0b10
 For value 2 , After ^x Operation. bin(result) =  0b11 , bin(x) =  0b10
Result =  3 

 For value 3 , Before ^x Operation. bin(result) =  0b11 , bin(x) =  0b11
 For value 3 , After ^x Operation. bin(result) =  0b0 , bin(x) =  0b11
Result =  0 

 For value 1 , Before ^x Operation. bin(result) =  0b0 , bin(x) =  0b1
 For value 1 , After ^x Operation. bin(result) =  0b1 , bin(x) =  0b1
Result =  1 

 For value 2 , Before ^x Operation. bin(result) =  0b1 , bin(x) =  0b10
 For value 2 , After ^x Operation. bin(result) =  0b11 , bin(x) =  0b10
Result =  3 

 For value 3 , Before ^x Operation. bin(result) =  0b11 , bin(x) =  0b11
 For value 3 , After ^x Operation. bin(result) =  0b0 , bin(x) =  0b11
Result =  0 

 For value 1 , Before ^x Operation. bin(result) =  0b0 , bin(x) =  0b1
 For value 1 , After ^x Operation. bin(result) =  0b1 , bin(x) =  0b1
Result =  1 

 For value 4 , Before ^x Operation. bin(result) =  0b1 , bin(x) =  0b100
 For value 4 , After ^x Operation. bin(result) =  0b101 , bin(x) =  0b100
Result =  5 

 For value 4 , Before ^x Operation. bin(result) =  0b101 , bin(x) =  0b100
 For value 4 , After ^x Operation. bin(result) =  0b1 , bin(x) =  0b100
Result =  1 

1

Process finished with exit code 0

Thanks,
Om

Couple of observations:
1. Your assignment states that in the sequence only one number is odd. In the code you pass sequence with multiple odd numbers.
2. If you pass different sequence, result is not as expected.
e.g.

print(find_it([2,3,1,2,3,1]))

Output:
0

(Oct-25-2020, 06:30 AM)omm Wrote: [ -> ]Question:
For a given list of numbers, only one digit is repeated odd number of times. Pass the list through function and return the number which is repeated odd number of times.

Sorry for the confusion. I did not write the question right earlier and I have corrected now. It has to return the only number which is repeated odd number of times (need not be an odd number). Example: [3,2,3,2,2]. Here, 2 is repeated 3 times and we need to return the number 2.

Thanks.

Please, don't edit post after you get reply. Now my post does not correspond to the content of your post.

(Oct-25-2020, 09:21 AM)buran Wrote: [ -> ]Please, don't edit post after you get reply. Now my post does not correspond to the content of your post.

Got it. Would never repeat it.

A number, XOR'd with itself, will be 0. So, each digit, if present an even number of times, wipes itself out to 0. If an odd number of times then one time will be left (if present 7 times, the first 6 xor to 0, then 0 xor the digit is the digit).

A number XOR itself is zero, and a number XOR with zero is the number.

3 ^ 3 == 0 and 3 ^ 0 == 3, therefore (3 ^ 3) ^ 3 == 3.

If we sort the numbers and put them in groups:
[1,2,3,1,2,3,1] == [1,1,1,2,2,3,3] == [[1,1,1], [2,2], [3,3]]

It should be easy to see that.
1^1^1 == (1^1)^1 == 0^1 == 1
2^2 == 0
3^3 == 0

And that:
(1^0)^0 == 1^0 == 1

Another way to think about this is to group numbers into pairs knowing that the XOR
of each pair is zero:
1,2,3,1,2,3,1] = [1,1,1,2,2,3,3] = [[1,1], [1], [2,2], [3,3]] == [0, 1, 0, 0]
(0^1)^(0^0) == 1^0 == 1
The pairs cancel each other out!

But does this hold true if the numbers are placed in a different order? Think of the bits as a row of switches. All switches start off (0). When you XOR a number you toggle the switches associated with the bits that are set (1) in the number.

Output:
switch  Number
0000    0110   0^6 = 6
0110    0011   (0^6)^3 = 5
0101    0110   ((6^2)^3)^6) = 3
0011
flipped 0231

The switches that are flipped an odd number of times end up being on (1), and the switches flipped an even number of times end up being off (0). Looking at the example it should be obvious that the order of the numbers does not affect how many times each switch is flipped.

This is bad code. It is certainly clever, and it does a good job starting a conversation about XOR and maybe leading to deeper understanding, but it is bad code. Good code requires thinking to write, but once written it should be very easy to understand.

This code is also bad because it is not flexible. This code only works if there is one number in the list that appears an odd number of times. This same logic cannot be used as the foundation for a function that returns a list of all numbers that appear in a list an odd number of times.

Finally this code is bad because it quietly gives a bad result if the list does not meet all the requirements. Look what happens if if there are more than one number that appears an odd number of times:
[1,1,2,2,2,3,3,3] == [[1,1],[2,2],[2],[3,3],[3]] == [0,0,2,0,3] == 2^3 == 1 # What?

If there is supposed to only be one number that appears an odd number of times and two or more numbers appearing and odd number of times is an error, I would prefer the code raises an exception instead of giving me a nonsensical number.

Thanks for the clear and elaborate explanation.

(Oct-26-2020, 04:09 AM)deanhystad Wrote: [ -> ]A number XOR itself is zero, and a number XOR with zero is the number.

3 ^ 3 == 0 and 3 ^ 0 == 3, therefore (3 ^ 3) ^ 3 == 3.

If we sort the numbers and put them in groups:
[1,2,3,1,2,3,1] == [1,1,1,2,2,3,3] == [[1,1,1], [2,2], [3,3]]

It should be easy to see that.
1^1^1 == (1^1)^1 == 0^1 == 1
2^2 == 0
3^3 == 0

And that:
(1^0)^0 == 1^0 == 1

Another way to think about this is to group numbers into pairs knowing that the XOR
of each pair is zero:
1,2,3,1,2,3,1] = [1,1,1,2,2,3,3] = [[1,1], [1], [2,2], [3,3]] == [0, 1, 0, 0]
(0^1)^(0^0) == 1^0 == 1
The pairs cancel each other out!

But does this hold true if the numbers are placed in a different order? Think of the bits as a row of switches. All switches start off (0). When you XOR a number you toggle the switches associated with the bits that are set (1) in the number.

Output:
switch  Number
0000    0110   0^6 = 6
0110    0011   (0^6)^3 = 5
0101    0110   ((6^2)^3)^6) = 3
0011
flipped 0231

The switches that are flipped an odd number of times end up being on (1), and the switches flipped an even number of times end up being off (0). Looking at the example it should be obvious that the order of the numbers does not affect how many times each switch is flipped.

This is bad code. It is certainly clever, and it does a good job starting a conversation about XOR and maybe leading to deeper understanding, but it is bad code. Good code requires thinking to write, but once written it should be very easy to understand.

This code is also bad because it is not flexible. This code only works if there is one number in the list that appears an odd number of times. This same logic cannot be used as the foundation for a function that returns a list of all numbers that appear in a list an odd number of times.

Finally this code is bad because it quietly gives a bad result if the list does not meet all the requirements. Look what happens if if there are more than one number that appears an odd number of times:
[1,1,2,2,2,3,3,3] == [[1,1],[2,2],[2],[3,3],[3]] == [0,0,2,0,3] == 2^3 == 1 # What?

If there is supposed to only be one number that appears an odd number of times and two or more numbers appearing and odd number of times is an error, I would prefer the code raises an exception instead of giving me a nonsensical number.