Can someone help me with approach to this problem(interview question)

Alice has arranged n bulbs in a row. The on bulbs are represented with character O and off bulbs are represented with character X. She is having one switch , which can turn on and off only the first bulb from the left. Every time she presses the switch, the state of the bulb toggles.

These bulbs are having a special feature, a bulb can switch its state automatically if the bulb in its left gets turned off. Alice presses the switch k times.

Task
determine the final state of all the bulbs.

Example
K=2
S=OOXOX
for 1st switch press
S=XXOOX
for 2nd switch press OXOOX
ans=OXOOX

1<=T<=10^5
1<=K<=10^18
1<=length of string<=60

1 Like

Thanks, but constraints for k are too high, and the time limit is 1 second.

since when interview questions are having time limits :joy:

I will provide you the solution only if you give the link

1 Like

@suru1907

ur solution for BNSONSTR matches with hundreds of solutions .
just variables changed
https://www.codechef.com/viewsolution/47965906

2 Likes

Maybe this is why he suggested O(N*K) solution . :joy:

1 Like

still dont understand how did he write such brute solution after seeing constraints .

1 Like

@nandamuripavan we can see this is your fake account, creating fake accounts for asking doubt arouses our suspicion, could you share the link to the problem?

1 Like