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

general
1

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

3 Likes
4

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

5

since when interview questions are having time limits :joy:

6

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

2 Likes
7

@suru1907

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

2 Likes
8

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

1 Like
9

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

1 Like
11

Well today i saw the exact same question in shop up coding round VIT Vellore campus placement. I applied brute it gave TLE

12

Had the same question asked to me now. had 1 hour and I blew it, But now I managed to solve it :wink:
here’s the solution I came up with, basically what you’ve to do is swap the first bulb no matter what. then, for the remaining series of bulbs we’ve to check for the special case and whether transition/change has occurred

const Alice = (K, S) => {
 var arr = S.split(""); // split given text into array
 var prevTrans; // Transition flag

 // Switch pressed 'K' times [loop]
 for (var k = 0; k < K; k++) {
  // Swap the first bulb
  arr[0] = arr[0] == "X" ? "O" : "X";
  prevTrans = true;

  //  Loop thru remaining bulbs
  for (var i = 1; i < arr.length; i++) {
   // check if prev State changed
   if (prevTrans) {
    if (arr[i - 1] == "X") {
     // Special feature case (swap if bulb is OFF)
     arr[i] = arr[i] == "X" ? "O" : "X";
    } else {
     // No change..
     prevTrans = false;
    }
   }
  }
 }

 console.log(arr.join("")); //OXOOX
};

Alice(2, "OOXOX");
13

TC - O(n*t) , n = length of input string
t = no of test cases.
SC - O(1)

#include <bits/stdc++.h>
using namespace std;
string fun(string s, long long int k){
char p;
for(int i=0;i<s.length();i++){
if(k%2!=0){
p=s[i];
s[i]=(s[i]==‘X’?‘O’:‘X’);
}
if(p==‘O’){
if(k%2!=0){
k=k/2 + 1;
}
else{
k=k/2;
}
}
else{
k=k/2;
}
}
return s;
}
int main() {
int t;
cin>>t;
while(t–){
string s;
long long int k;
cin>>k;
cin>>s;
cout<<fun(s,k)<<endl;
}
return 0;
}