# PROBLEM LINK:

*Author:* hareesh29

# DIFFICULTY:

EASY

# PREREQUISITES:

# PROBLEM:

GIven a string of length n. where the first k elements are “R” and the next n-k elements are “B”. we have to print Alice wins if(k>n-k) else print Bob wins

# EXPLANATION:

This is a classic binary search problem. The idea is to find the value of k using a modified binary search.

pseudo code of modified binary search binary search

```
while(s[first]=="R" and s[last]=="B"):
mid=(first+last)//2
if(s[mid]=="R"):
f=mid+1
elif(s[mid]=="B"):
l=mid-1
if(s[first]=="B"):
nr=first
nb=n-first
elif(s[last]=="R"):
nr=last+1
nb=n-nr
```

### Explanation:

Initially first=0 and last=n-1 and mid=(first+last)/2. Here logic is to find value of mid such that s[mid] is R and s[mid+1] =B or s[mid] is B and s[mid-1] is R.In the first case k=mid+1 and in the second case k=mid.now we have to just compare k and n-k.if k is greater than n-k then Alice wins else Bob wins .

# TIME COMPLEXITY

O(log(n))

# SOLUTIONS:

## Setter's Solution

```
for _ in range(int(input())):
n=int(input())
s=input()
f=0
l=n-1
while(s[f]=="R" and s[l]=="B"):
mid=(f+l)//2
if(s[mid]=="R"):
f=mid+1
elif(s[mid]=="B"):
l=mid-1
if(s[f]=="B"):
nr=f
nb=n-f
elif(s[l]=="R"):
nr=l+1
nb=n-nr
if(nr>nb):
print("Alice wins")
else:
print("Bob wins")
```