# PROBLEM LINK:

Contest Division 1

Contest Division 2

Contest Division 3

Practice

**Setter:** Prasant Kumar

**Tester & Editorialist:** Taranpreet Singh

# DIFFICULTY

Easy

# PREREQUISITES

None

# PROBLEM

Given a circular binary string s of length N, where you can perform operations on this string, flipping character from ‘0’ to ‘1’ and vice versa.

Determine the minimum number of operations needed to obtain a good string, where a circular string is good when it contains at least one occurrence of ‘1’ and for each ‘1’, distance to next ‘1’ is the same.

# QUICK EXPLANATION

- The distance between '1’s can only be a factor of N.Try all factors of N as distance.
- For each factor, try all possible start points. i.e. For distance d, there are d positions where ‘1’ should appear, and the rest string should be filled with zeros.
- Find minimum Hamming distance of given string to any of the valid strings found above.

# EXPLANATION

### Valid distance between '1’s

Let’s define the distance between two positiions i and j in 0-based indexing as j-i if i \leq j and j+N-i otherwise. Denoting distance by d(i, j).

Let’s suppose, we have a good string with k occurrences of 1s, and the distance between each ‘1’ from the next one is d. Assuming the positions of ones are p_1, p_2 \ldots p_k, we have d(p_i, p_{i+1}) = d for all 1 \leq i < k and d(p_k, p_1) = d as well.

We can see that starting from p_1, moving to next p_i until reaching p_1 again, leads to visiting N positions exactly once. So, we can claim that d*k = N holds.

**Claim:** If a circular string of length N is good, then the distance between each ‘1’ and the next ‘1’ is a factor of N.

Hence, let us try all divisors d one by one, and compute the minimum number of operations needed to convert s into a good string with distance d between ones.

### All good string s with distance d

Let’s suppose we fix the distance between each ‘1’ and the next as d where d is a factor of N.

The circular binary string would look like ‘1’ followed by d-1 ‘0’, then ‘1’ followed by d-1 '0’s and so on, covering the whole string. For N = 6, d = 3, we get string `100100`

.

But there are string `010010`

and string `001001`

as well with d = 3.

We need to fix the position of the first occurrence f of ‘1’ in the string, as the first occurrence, as f and d defines the whole good circular string uniquely.

Pair (f, d) represent a string with each ‘1’ having distance d from the next one, and position f contains ‘1’. We can see that for each position p, it contains ‘1’ if and only if p \bmod d = f, and ‘0’ otherwise.

### Computing minimum Hamming distance to good string

Let’s try pair (f, d), representing string T, and try to compute its hamming distance from given string s. We know that T contains exactly N/d ones, and the rest zeros, so let’s iterate on those positions. Let’s make a set A denoting the set of positions of '1’s in T.

We need to count the number of positions p in set A such that s_p = ‘0’, and number of positions not in A such that s_p = ‘1’, as the sum of these values would be the hamming distance.

Let c denote the number of ones in whole string s, and x denote the number of ones in positions in set p present in set A such that s_p = ‘1’. We can see that The hamming distance is (N/d - x) + (c-x) \implies N/d + c - 2*x.

## In case you missed

N/d -x is the number of positions where T contains ‘1’, but s contains ‘0’, and (c-x) denote the number of positions where T contains ‘0’ but s contains ‘1’

We can compute c beforehand, and compute x, the number of ones at positions p such that p \bmod d = f, in time O(N/d) time by following loop.

```
x = 0
for(int p = f; p < N; p += d)
if(s[p] == '1')
x++
```

Hence, we shall try all valid pairs (f, d) one by one, compute Hamming distance from string s, and print minimum.

### Time complexity analysis

For a fixed distance d, let’s consider all start points f. There are exactly d unique choices for f, and computing each one takes N/d iterations, leading to total N iterations.

Hence, for each factor d of N, we need O(N) time, leading to time complexity O(N*\sigma(N)), where \sigma(N) is the divisor function.

# TIME COMPLEXITY

The time complexity is O(N*\sigma(N)) per test case.

# SOLUTIONS

## Setter's Solution

```
#include<bits/stdc++.h>
using namespace std;
signed main(){
// freopen("input.txt", "r", stdin);
int t;cin>>t;
while(t--){
int n;cin>>n;
string s;cin>>s;
int sum=0;
for(int i=0;i<n;i++){
sum+=s[i]-'0';
}
int ans=n;
for(int x=1;x<=n;x++){
if(n%x)continue;
for(int j=0;j<x;j++){
int temp=0;
for(int k=j;k<n;k+=x){
if(s[k]=='1'){
temp-=1;
}else temp+=1;
}
ans=min(ans,sum+temp);
}
}
cout<<ans<<endl;
}
return 0;
}
```

## Tester's Solution

```
import java.util.*;
import java.io.*;
class BinaryStringOnSteroid{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int N = ni();
char[] C = n().toCharArray();
int count = 0;
for(int i = 0; i< N; i++)count += C[i]-'0';
int ans = N;
for(int d = 1; d <= N; d++){
if(N%d != 0)continue;
for(int st = 0; st < d; st++){
int cur = 0;
for(int j = st; j< N; j += d)
cur += C[j]-'0';
int op = N/d+count-2*cur;
ans = Math.min(ans, op);
}
}
pn(ans);
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
static boolean multipleTC = true;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new BinaryStringOnSteroid().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
```

Feel free to share your approach. Suggestions are welcomed as always.