* Author:* Jaskaran Singh

*Rahul Sharma*

**Tester:***Rahul Sharma*

**Editorialist:**# DIFFICULTY:

EASY

# PREREQUISITES:

Strings, observation, basic math

# PROBLEM:

Beeds Arranging game is described by a string of length nn consisting of characters “.” (empty space) and “*” (beed). In one move you can shift beed to one unit left or one unit right, only if the corresponding place *exists and is empty*. The game ends up as soon as the beeds are lined up, that is, there should not exist any empty cells between any beeds.

FInd minimum number of moves.

# EXPLANATION:

Let’s denote k the number of beads in the string, and x_q,x_2,...,x_k (1 \leq x_1<x_2<...<x_k \leq n) their positions in the string.

Note that in the optimal solution the beed with number m=ceil(n/2) will not make moves. This can be proved by considering the optimal solution in which the beed with the number m makes at least one move and come to the conclusion that this solution is not optimal. Consider beed with numbers from i=1 to n. Then the final position of the $i^{th} beed will be x_m-m +i, and the answer will be \sum|xi−(x_m−m+i)| where i runs from 1 to k.

# COMPLEXITIES:

**Time Complexity:** O(N) for each test case

# SOLUTIONS:

## Setter's Solution

```
#include<bits/stdc++.h>
using namespace std;
void solve()
{
int n;
cin >> n;
string s;
cin >> s;
int cnt = 0;
for(auto x : s)
cnt += (x == '*' ? 1 : 0);
int pos = -1;
int cur = -1;
for(int i = 0; i < n; i++)
{
if(s[i] == '*')
{
cur++;
if(cur == cnt / 2)
pos = i;
}
}
long long ans = 0;
cur = pos - cnt / 2;
for(int i = 0; i < n; i++)
if(s[i] == '*')
{
ans += abs(cur - i);
cur++;
}
cout << ans << endl;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int tc = 1;
cin >> tc;
for(int i = 0; i < tc; i++)
{
solve();
}
}
```