Binary String on Steroids Codechef Solution in Java| AskTheCode

Codechef June Cook-Off 2021 Solution | Binary String on Steroids (BNSONSTR) | AskTheCode

---

Problem:

A circular binary string is called good if it contains at least one character '1' and there is an integer d such that for each character '1', the distance to the nearest character '1' clockwise is d.

You are given a circular binary string S with length N. You may choose some characters in this string and flip them (i.e. change '1' to '0' or vice versa). Convert the given string into a good string by flipping the smallest possible number of characters.

---

Input:

• The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.

• The first line of each test case contains a single integer N.

• The second line contains a single string S with length N.

---

Output:

Print a single line containing one integer ― the minimum number of flips required to transform the initial string into a good string.

---

Sample Input:

2
6
110011
4
0001

---

Sample Output:

2
0

---

Code:

/* package codechef; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		Scanner scan = new Scanner(System.in);
		int test = scan.nextInt();
		while(test-- > 0)
		{
		    int n = scan.nextInt(),ones = 0,d,i,start_1 ;
		    int zeros_one,acc_ones,ones_zeros,curr,ind;
		    String s = scan.next();
		    for(i =0;i<n;i++)
		    {
		        if(s.charAt(i) == '1')
		        {
		            ones++;
		        }
		        
		    }
		    if(ones == 0)
		    {
		        System.out.println(1);
		        continue;
		    }
		    else if(ones == 1)
		    {
		        System.out.println(0);
		        continue;
		    }
		    
		    int ans = Integer.MAX_VALUE;
		    for(d =1;d<=n;d++)
		    {
		        if(n%d == 0)
		        {
    		        for(start_1 = 0;start_1 <d;start_1++)
    		        {
    		            zeros_one = 0; ind = start_1;
    		            while(true)
    		            {
    		                if(s.charAt(ind) == '0')
    		                {
    		                    zeros_one++; 
    		                }
    		                ind = (ind+d)%n;
    		                if(ind == start_1)
    		                    break;
    		            }
    		            acc_ones = n/d;
    		            ones_zeros = ones-(acc_ones-zeros_one);
    		            curr = ones_zeros+zeros_one;
    		            ans = Math.min(ans,curr);
    		        }
		        }
		    }
		    
		    System.out.println(ans);
		}	    
	}
}