#🔒 : Given an array of n positive numbers. All numbers occurs even number of times except 1 whichoccu

167 messages · Page 1 of 1 (latest)

shell heart
#

def find_odd_occ(arr):
result = 0
for number in arr:
result ^= number
return result

Example usage

arr = [1, 2, 3, 2, 3, 1, 3]
print(find_odd_occ(arr)) # Output: 3

vital relicBOT
#

Hey @shell heart!

It looks like you're trying to paste code into this channel.

Discord has support for Markdown, which allows you to post code with full syntax highlighting. Please use these whenever you paste code, as this helps improve the legibility and makes it easier for us to help you.

To do this, use the following method:
```py
print('Hello, world!')
```

This will result in the following:

print('Hello, world!')```
You can **edit your original message** to correct your code block.
vital relicBOT
#

@shell heart

Python help channel opened

Remember to:

  • Ask your Python question, not if you can ask or if there's an expert who can help.
  • Show a code sample as text (rather than a screenshot) and the error message, if you've got one.
  • Explain what you expect to happen and what actually happens.

:warning: Do not pip install anything that isn't related to your question, especially if asked to over DMs.

Closes after a period of inactivity, or when you send !close.
pseudo hamlet
shell heart
#

Yes I do not understand the dry run of this code

stone geode
#

Do you understand what ^= does?

pseudo hamlet
#

what does 'dry run' mean?

shell heart
shell heart
stone geode
#

What are you unsure of?

#

Do you understand function definitions? Do you understand loops?

shell heart
#

yes i understand all of that, the only issue is that i am unable to understand it is working, i know that even ones are cancelling out, odd one would remain

#

but how is that carrying out, i do not understand

stone geode
#

what do you think ^= does?

shell heart
#

that is the confusion

stone geode
shell heart
#

okay maybe there is the confusion

stone geode
#

do you understand what binary and bits are?

shell heart
#

yes i understand

stone geode
#

What are they?

shell heart
#

binary are 0 and 1

stone geode
#

yes, but how are they used?

#

do you understand binary counting?

shell heart
#

yes i understand them

stone geode
#

ok

#

so ^ will flip bits

#

we're using ^= to flip bits on and off. If the same number's bits are flipped twice, it's like it never happened

#

this will happen with any number that appears an even number of times

shell heart
#

i understand this result = 0
result ^= 1 => result = 0 ^ 1 = 1
result ^= 2 => result = 1 ^ 2 = 3
result ^= 3 => result = 3 ^ 3 = 0
result ^= 2 => result = 0 ^ 2 = 2
result ^= 3 => result = 2 ^ 3 = 1
result ^= 1 => result = 1 ^ 1 = 0
result ^= 3 => result = 0 ^ 3 = 3
but i do not understand how is this saying 3 got odd count

stone geode
#

!e

result = 11

print(f'{result:08b}')
vital relicBOT
stone geode
#

look at the binary for 11

#

!e

result = 11

print(f'{result:08b}')
result ^= 11
print(f'{result:08b}')
vital relicBOT
stone geode
#

if we ^= (XOR) the bits, they all get turned off

#

so xor'ing a number twice is basically the same as not xor'ing it at all

#

if a number gets xor'd an odd number of times, that means the bits will remain on

#

whatever bits are on at the end of the loop would be the bits of the number that appeared an odd amount

shell heart
#

ok but can you explain what u just said with reference to this
result = 0
result ^= 1 => result = 0 ^ 1 = 1
result ^= 2 => result = 1 ^ 2 = 3
result ^= 3 => result = 3 ^ 3 = 0
result ^= 2 => result = 0 ^ 2 = 2
result ^= 3 => result = 2 ^ 3 = 1
result ^= 1 => result = 1 ^ 1 = 0
result ^= 3 => result = 0 ^ 3 = 3

stone geode
#

the actual resulting number in base 10 (decimal) isn't necessarily useful to view

#

it's the bits that are important

pseudo hamlet
stone geode
#

!e

def find_odd_occ(arr):
    result = 0
    for number in arr:
        result ^= number
        print(f'{number:04b} {result:04b}')
    return result


arr = [1, 2, 3, 2, 3, 1, 3]
print(find_odd_occ(arr))  # Output: 3
vital relicBOT
stone geode
#

the binary number on the left is the number we're checking, and the binary number on the right is the result (the bits that are currently on/off)

shell heart
stone geode
#

!e

def find_odd_occ(arr):
    result = 0
    for number in arr:
        result ^= number
        print(f'flipping {number} -- {number:04b} {result:04b}')
    return result


arr = [1, 2, 3, 2, 3, 1, 3]
print(find_odd_occ(arr))  # Output: 3
vital relicBOT
shell heart
shell heart
#

Initial Setup: result starts at 0.
First Number (1):
0
⊕
1

1
0⊕1=1. Now, result is 1.
Second Number (2):
1
⊕
2

3
1⊕2=3. Now, result is 3.
Third Number (3):
3
⊕
3

0
3⊕3=0. The two 3s cancel each other out, result goes back to 0.
Fourth Number (2):
0
⊕
2

2
0⊕2=2. Now, result is 2.
Fifth Number (3):
2
⊕
3

1
2⊕3=1. Now, result is 1.
Sixth Number (1):
1
⊕
1

0
1⊕1=0. The two 1s cancel each other out, result goes back to 0.
Seventh Number (3):
0
⊕
3

3
0⊕3=3. This is the third occurrence of 3, and result becomes 3.

i was asking chatgpt, it explained me this is the way cancellation is being performed, how is the first occurrence of 3 cancelling out the second occurence of 3 when it only appeared once

pseudo hamlet
shell heart
pseudo hamlet
shell heart
pseudo hamlet
# shell heart Okay

it's that when you do a ^ x, it'll flip a very specific set of bits in a; these flips are exactly canceled out if you do another ^ x on it

#

so if you do ^ x an even number of times, it's like doing nothing at all
since only 1 number in the entire array appears odd times, by the end of doing result ^ x for every number x inside of arr, it's like you only did result ^ o where o is the number that appears an odd number of times

shell heart
#

Alright

stone geode
# shell heart Alright

imagine a wall of lightswitches. Each number represents a specific set of lightswitches to interact with

#

if the switch is on, turn it off, if it's off, turn it on

#

if you perform the same instruction twice, it's like you did nothing at all

shell heart
stone geode
#

1 means the lightswitch is on, 0 means it is off

shell heart
shell heart
stone geode
# 
flipping 1 -- 0001 0001
#

the binary number on the left is the instructions

#

the binary number on the right is what switches are currently on/off

# 
0001 0001
#

so for the first one, we're saying flip the switch on the right

# 
0010 0011
#

the next one says flip the 3rd switch

#

so now switch 3 and 4 are on

#

0011 0000

#

The next instruction is to flip 3 and 4

#

now they are both off

#

0010 0010

#

then we flip 3

#

and so on

#

!e

def find_odd_occ(arr):
    result = 0
    for number in arr:
        result ^= number
        print(f'flipping {number} -- {number:04b} {result:04b}')
    return result


arr = [1, 2, 3, 2, 3, 1, 3]
arr.sort()
print(find_odd_occ(arr))  # Output: 3
vital relicBOT
stone geode
#

maybe it's clearer if we sort the list first

shell heart
#

Okay got it

shell heart
stone geode
#

0011 is the binary for 3

#

it's the only number that flipped its bits on and never flipped them off

#

@shell heart

shell heart
#

So the right hand side answers be it decimal or binary don't mean anything, they are just switches?

#

@stone geode

stone geode
#

1 sec

#

ok, I wrote a quick function that will display a number's bits as "on/off" instead of 0 1

#

!e

instructions = ['off', 'on']

def bin_to_instructions(dig):
    for i in f'{dig:04b}':
        print(instructions[int(i)], end='|')
    print()


bin_to_instructions(2)
vital relicBOT
shell heart
stone geode
#

I'm putting together an example

#

but I want you to follow what I'm doing

#

!e

instructions = ['OFF', 'ON']

def bin_to_instructions(dig):
    results = []
    for i in f'{dig:04b}':
        results.append(instructions[int(i)])
    return '|'.join(results)


def find_odd_occ(arr):
    result = 0
    for number in arr:
        #result ^= number
        print(number, bin_to_instructions(number))
    return result


arr = [1, 2, 3, 2, 3, 1, 3]
#arr.sort()
find_odd_occ(arr)
vital relicBOT
stone geode
#

These are each number's instructions

#

1 says OFF OFF OFF ON

#

3 says OFF OFF ON ON

#

maybe this isn't clear because OFF doesn't actually mean "turn it off"

#

the way it's being used is "FLIP"

shell heart
#

But how it is doing 4 times?

stone geode
#

it's checking each bit

#

we can technically ignore the first two instructions since we're dealing with small numbers

#

!e

instructions = ['....', 'FLIP']

def bin_to_instructions(dig):
    results = []
    for i in f'{dig:02b}':
        results.append(instructions[int(i)])
    return '|'.join(results)


def find_odd_occ(arr):
    result = 0
    for number in arr:
        #result ^= number
        print(number, bin_to_instructions(number))
    return result


arr = [1, 2, 3, 2, 3, 1, 3]
#arr.sort()
find_odd_occ(arr)
shell heart
#

But that's just binary conversion

vital relicBOT
stone geode
#

let's look at this insatead

#

imagine a wall

#

with two lightswitches

shell heart
#

That's just binay conversion i realised

stone geode
#

at the start of the program, both lightswitches are off

#

each number (1, 2, 3) has instructions associated with it

#

1 is "ignore the left switch, flip the right switch"

#

so that means if it's on, turn it off

#

if it's off, turn it on

#

does this make sense?

shell heart
#

But that is just binary conversion of 1

stone geode
#

yes

shell heart
#

But that's not the solution of the question

stone geode
#

code is a series of steps

#

it's not just about the solution

#

I'm not talking about the solution, I'm talking about the process that leads to the solution

shell heart
#

ok but can you explain what u just said with reference to this
result = 0
result ^= 1 => result = 0 ^ 1 = 1
result ^= 2 => result = 1 ^ 2 = 3
result ^= 3 => result = 3 ^ 3 = 0
result ^= 2 => result = 0 ^ 2 = 2
result ^= 3 => result = 2 ^ 3 = 1
result ^= 1 => result = 1 ^ 1 = 0
result ^= 3 => result = 0 ^ 3 = 3

stone geode
#

That's what I'm doing

#

I'm simplifying it

#

because you didn't understand

shell heart
#

No sorry, i was just pasting this and was trying to explain what m stuck at

stone geode
#

and I'm explaining it in simpler terms so you understand it

shell heart
stone geode
#

it's the current "state" of the switches

#

yes

#

converted from binary back into decimal

#

but we don't really care about the decimal

shell heart
#

that i know

stone geode
#

then I'm not sure what you're asking

shell heart
#

that they are decimal

stone geode
#

whatever the final state of the switches is when the loop finishes is the solution

shell heart
stone geode
#

because when the code finishes, the switches are ON ON

#

which is 11

shell heart
#

i got when you told as its switch is the only one which is left on

stone geode
#

11 is binary for 3

#

00 is 0
01 is 1
10 is 2
11 is 3

shell heart
#

that also i know, just bear one more time with me. in that case ure telling me that
1= off on
3=on on
0=off off
2=on off
1=off on
0=off off
3=on on
this is the answer but how does that make sense

stone geode
#

because performing the same set of instructions twice negates it

#

go find two lightswitches and try it out

#

it will help you understand

#

!e

instructions = ['....', 'FLIP']

def bin_to_instructions(dig):
    results = []
    for i in f'{dig:02b}':
        results.append(instructions[int(i)])
    return '|'.join(results)


def find_odd_occ(arr):
    result = 0
    for number in arr:
        result ^= number
        print(number, bin_to_instructions(result))
    return result


arr = [1, 2, 3, 2, 3, 1, 3]
arr.sort()
find_odd_occ(arr)
vital relicBOT
stone geode
#

remember what it looked like sorted

#

notice how every other result shows everything off

#

we turn on right, we turn it off

#

we turn on left, we turn it off

#

we turn on both, we turn them both off

#

then we turn them both on, and leave them on

#

since there's an odd amount of instructions

shell heart
stone geode
#

yes

#

the bits act as a series of on/off switches

#

that's what binary is

shell heart
#

result = 0
result ^= 1 => result = 0 ^ 1 = 1
result ^= 2 => result = 1 ^ 2 = 3
result ^= 3 => result = 3 ^ 3 = 0
result ^= 2 => result = 0 ^ 2 = 2
result ^= 3 => result = 2 ^ 3 = 1
result ^= 1 => result = 1 ^ 1 = 0
result ^= 3 => result = 0 ^ 3 = 3
code is actually doing this

stone geode
#

^ acts on the binary of a number

shell heart
#

okay

vital relicBOT
#
Python help channel closed

This help channel has been closed and it's no longer possible to send messages here. If your question wasn't answered, feel free to create a new post in #1035199133436354600. To maximize your chances of getting a response, check out this guide on asking good questions.