Finding switches by divisors

Question

There are N switches (from 1 to N) and also N bulbs (from 1 to N).

the switch is can be pressed only once and it can turn ON/OFF the bulb. a switch can turn ON/OFF more than 1 bulbs.

For example: The switch number 12 can turn ON/OFF the bulbs {1, 2, 3, 4, 6, 12} (because {1, 2, 3, 4, 6, 12} are the divisors of 12)

So we have a function main(N,setON)

N is the number of lights
SetOn is set of bulbs that are from the beginning are ON

The function must return list of switches that are served to turn ON all the bulbs

For example given, N=6 and setON = {2,4}, return the list [2,5,6]

after pressed the button 2 will light on {1,4} bulbs
after pressed the button 5 will light on {4,5} bulbs
after pressed the button 6 will light on {1,2,3,4,5,6} bulbs

I started this question but I'm out of ideas how to solve this. I did it in way that I call a function divisors that finds for each number the divisors and after it returns a list of divisors of number N and then I run a loop for each list to see where it turns ON or OFF and put the number of the switch to a new list. But I actually don't get the result that I want, and I'm out of ideas.

I would like to here your suggestions, I'm not requesting of you solve my problem, just give me a hint :) or if you want correct me.

import math
def main(N, setON):
    newList= []
    acces = set(range(1,N+1))
    turnOFF = set()
    for number in range(N,1,-1):
        divs = divisors(number)                    
        for i in divs:
            if i in setON:
                turnOFF.add(i)
                setON.remove(i)
            else:
                setON.add(i)
                if i in turnOFF:
                    turnOFF.remove(i)
        newList.append(divs[-1])
        if len(setON) == N-1:
            print(newList)


def divisors(n):
    divs = [x for x in range(1, int(math.sqrt(n))+1) if n % x == 0]
    opps = [int(n/x) for x in divs]
    return list(set(divs + opps))


N=6
setON={2,4}
main(N, setON)

It gives me [6, 5, 4]

I'm confused by your divisors function. Shouldn't it return [x for x in range(1, n+1) if x%n ==0]? — mauve, Oct 26 '18 at 14:37
In case of your given example `given, N=6 and setON = {2,4}, return the list [2,5,6]` I think the answer should be just [5,6], because when 4 was already set on the switches which are divisors of 4 are also setON therefore with [2,4] the switches that are already set ON are [1,2,4] remaining switches need to set ON are 3, 5, 6 , now when you switch ON 6 you switch ON 1, 2, 3, 6 - so 3 is picked. When you switch on 5, you switch 1, 5 -> 5 is picked. Answer is [5,6]. If not please let me know why not ? — SomeDude, Oct 26 '18 at 14:50
@mauve in my code it give the list of the divisors, for example if N is 6 so it gives [1, 2, 3, 6] for N =5 [1, 5] , for every iteration in range(N,1,-1) — LordNord, Oct 26 '18 at 15:08
@SomeDude No because as I wrote the switch can also turn off the light, for example: if we have N=6 and setON = {2,4} ,switch 6 turns off light number 2 and turns 1,3,6 so we have {1,3,4,6}, When we press switch 5 we turn off the light 1, turn the light 5 on so we have {3,4,5,6} by adding switch 2 we actully adding 1,2 lamps and we have complete set {1,2,3,4,5,6} — LordNord, Oct 26 '18 at 15:15

score 2 · Answer 1 · answered Oct 26 '18 at 14:37

2

Start with the highest-numbered switch and work your way down.

If switch X is the highest switch you can toggle, then it is the only one that can change bulb X, so look at bulb X to see if that switch has to be on or off.

Switch X is then determined -- if it has to be on, then toggle the bulbs for its divisors and proceed to the next smallest switch, because that one is now the highest switch you can change.

Proceed until you're out of switches. Either all the bulbs are on or there is no answer.

answered Oct 26 '18 at 14:37

Matt Timmermans

53,709
3
46
87

Thank you for the answer, I'm sorry I didn't understand,English is not my mother language :( I understood for example if 6 is the only one that can turn on the light 6 so it should be ON. but I didn't get it " then toggle the bulbs for its divisors and proceed to the next smallest switch" could you give me an example please – LordNord Oct 26 '18 at 15:06
Start with 12, because no other switch will light it. Once that is lit, proceed to the next light that is off and deal with that. (11 in this case). Proceed down to 10, since 10 is still off. When you reach a light that is on, you can skip that and go to the next light that is still off. – mauve Oct 26 '18 at 15:26

juvian · Accepted Answer · 2018-10-26T15:31:42.897

0

Your code is mostly correct but you are switching bulbs when they are already on, which makes an incorrect answer. Also you are not checking bulb 1, and the check of are all on is wrong too. Here is fixed version of yours:

for number in range(N,0,-1):
    if number in setON:
        continue
    #your previous code
    if len(setON) == N:
        print(newList)

Here is a faster (avoids using sets) and a bit cleaner implementation:

import math
def main(N, setON):
    isOn = [False] * (N + 1)
    for bulb in setON:
        isOn[bulb] = True

    answer = []

    for x in range(N, 0, -1):
        if not isOn[x]:
            for num in divisors(x):
                isOn[num] = not isOn[num]
            answer.append(x)

    if sum(isOn) == N:        
        return list(reversed(answer))            



def divisors(n):
    divs = [x for x in range(1, int(math.sqrt(n))+1) if n % x == 0]
    opps = [int(n/x) for x in divs]
    return list(set(divs + opps))


N=6
setON={2,4}
print(main(N, setON))

edited Oct 26 '18 at 15:31

answered Oct 26 '18 at 15:26

juvian

15,875
2
37
38

You are right, your code is better,thank you for giving me another point of view to solve this problem, it will help me also with other problems. – LordNord Oct 26 '18 at 21:14
Could you please explain why you added [False] * (N + 1), it will be 7 posts , and the function of sum isn't it for summing of integers? Thank you – LordNord Oct 26 '18 at 21:25
@LordNord [False] * (N) would be enough memory, but would then need to be careful on indexes, as isOn[0] represents if 1 is on or not. That would lead to do isOn[x - 1] or isOn[num - 1]. It is much easier to waste 1 space and make indexes match our input, less risks of bugs too. As for your second question, its one of many possibilities [explained here](https://stackoverflow.com/questions/12765833/counting-the-number-of-true-booleans-in-a-python-list) – juvian Oct 26 '18 at 21:57

Finding switches by divisors

2 Answers2