Given a binary string S of length N, the task is to minimize the count of operations required to find a binary string T of the same length N such that:
- In one operation, it is allowed to flip any bit, i.e. convert 0 to 1 or vice versa.
- In the binary string T, choose a number K, such that:
- N is perfectly divisible by K, and
- The first K bits in T are 0, the next K are 1, the next K are 0, and so on.
Examples:
Input: S = 1011011
Output: 4
Explanation:
If we choose K = 1, then required string S=0101010, Moves required 4
If we choose K = 7, then required string S=0000000, Moves required 5
Values of K= 2, 3, 4, 5, 6 is not allowed because, it is not perfectly divide N = 7.
Choose K = 1. So, Final String is 0101010, Flip the first, second, third and seventh bit. Print 4 because string S satisfies all conditions after performing 4 moves.Input: S = 000001
Output: 1
Explanation:
If we choose K=1, then required string S=010101, Moves required 2
If we choose K=2, then required string S=001100, Moves required 3
If we choose K=3, then required string S=000111, Moves required 2
If we choose K=6, then required string S=000000, Moves required 1
So, Select K=6, So, output will be1.
Approach: The approach is based on the following observation:
It is mentioned in the problem statement itself that we have to choose K such that N is divisible by K, so we can break our problem into subproblem to find all the divisors of N and then find number of operations required for each of the divisor and choose the minimum number of operation between all of them.
Based on the above observation, follow the steps below to implement this approach:
- Find all the divisor of N (size of given string).
- For each divisor, Traverse the String and for each iteration:
- Count the number of changes required in given string if we choose the K = current divisor.
- If current changes required is less than the previous result then update it with the current result.
- Return the minimum changes required.
Below is the implementation of the above approach:
C++
// C++ code to implement above approach#include <bits/stdc++.h>using namespace std;// Function to find all divisors// of given string length n.void findAllDivisors(int n, vector<int>& v){ for (int i = 1; i <= sqrt(n); i++) { // Check whether the given number // is divisible by current number or not if (n % i == 0) { // Check if divisors are equal if (n / i == i) v.push_back(i); else { v.push_back(n / i); } } }}// Function to find the minimum// number of operation require to make// given substring alternative of size Kint findMinOperations(string& S){ int n = S.length(), result = n; // Find and store all divisors of n. vector<int> v; findAllDivisors(n, v); // For each divisor, // calculate minimum changes required. for (int i = 0; i < v.size(); i++) { // Count of operations required int count = 0; bool flag = false; for (int j = 0; j < n; j += v[i]) { for (int k = j; k < j + v[i] && k < n; k++) { if (flag && S[k] == '0') count++; if (!flag && S[k] == '1') count++; } flag = (flag == false); } // If current changes required // is less than previous result // then update result if (count < result) result = count; } return result;}// Driver codeint main(){ string S = "101101"; cout << findMinOperations(S); return 0;} |
Java
// Java code to implement above approachimport java.util.*;class GFG { // Function to find all divisors // of given string length n. static void findAllDivisors(int n, Vector<Integer> v) { for (int i = 1; i <= Math.sqrt(n); i++) { // Check whether the given number // is divisible by current number or not if (n % i == 0) { // Check if divisors are equal if (n / i == i) v.add(i); else { v.add(n / i); } } } } // Function to find the minimum // number of operation require to make // given substring alternative of size K static int findMinOperations(String S) { int n = S.length(); int result = n; // Find and store all divisors of n. Vector<Integer> v = new Vector<Integer>(); findAllDivisors(n, v); // For each divisor, // calculate minimum changes required. for (int i = 0; i < v.size(); i++) { // Count of operations required int count = 0; boolean flag = false; for (int j = 0; j < n; j += v.get(i)) { for (int k = j; k < j + v.get(i) && k < n; k++) { if (flag && S.charAt(k) == '0') count++; if (!flag && S.charAt(k) == '1') count++; } flag = (flag == false); } // If current changes required // is less than previous result // then update result if (count < result) result = count; } return result; } // Driver code public static void main(String[] args) { String S = "101101"; System.out.print(findMinOperations(S)); }}// This code is contributed by hrithikgarg03188. |
Python3
# Python3 program to implement the above approach# function to find all divisors of# given string length ndef findAllDivisors(n, v): for i in range(1, 1 + int(n ** 0.5)): # check whether the given number # is divisible by the current number or not if n % i == 0: # check if divisors are equal if (n // i) == i: v.append(i) else: v.append(n // i) return v# function to find the minimum# number of opertations required to make# given substring alternative of size Kdef findMinOperations(S): n = len(S) result = n # find and store all divisors of n v = [] v = findAllDivisors(n, v) for i in range(len(v)): # count of operations required count = 0 flag = False for j in range(0, n, v[i]): for k in range(j, min(j + v[i], n), 1): if (flag and S[k]) == "0": count += 1 if (not flag and S[k]) == "1": count += 1 flag = bool(flag == False) # if current changes required # is less than the previous result, # then, update the result if count < result: result = count return result# Driver CodeS = "101101"print(findMinOperations(S))# this code was contributed by phasing17 |
C#
// C# code to implement above approachusing System;using System.Collections;public class GFG{ // Function to find all divisors // of given string length n. static void findAllDivisors(int n, ArrayList v) { for (int i = 1; i <= Math.Sqrt(n); i++) { // Check whether the given number // is divisible by current number or not if (n % i == 0) { // Check if divisors are equal if (n / i == i) v.Add(i); else { v.Add(n / i); } } } } // Function to find the minimum // number of operation require to make // given substring alternative of size K static int findMinOperations(String S) { int n = S.Length; int result = n; // Find and store all divisors of n. ArrayList v = new ArrayList(); findAllDivisors(n, v); // For each divisor, // calculate minimum changes required. for (int i = 0; i < v.Count; i++) { // Count of operations required int count = 0; bool flag = false; for (int j = 0; j < n; j += (int)v[i]) { for (int k = j; k < j + (int)v[i] && k < n; k++) { if (flag && S[k] == '0') count++; if (!flag && S[k] == '1') count++; } flag = (flag == false); } // If current changes required // is less than previous result // then update result if (count < result) result = count; } return result; } // Driver code static public void Main (){ string S = "101101"; Console.Write(findMinOperations(S)); }}// This code is contributed by hrithikgarg03188. |
Javascript
// JavaScript code to implement above approach// Function to find all divisors// of given string length n.function findAllDivisors(n, v){ for (var i = 1; i <= Math.floor(Math.sqrt(n)); i++) { // Check whether the given number // is divisible by current number or not if (n % i == 0) { // Check if divisors are equal if (Math.floor(n / i) == i) v.push(i); else { v.push(Math.floor(n / i)); } } } return v;}// Function to find the minimum// number of operation require to make// given substring alternative of size Kfunction findMinOperations(S){ var n = S.length; var result = n; // Find and store all divisors of n. var v = []; v = findAllDivisors(n, v); // For each divisor, // calculate minimum changes required. for (var i = 0; i < v.length; i++) { // Count of operations required var count = 0; var flag = false; for (var j = 0; j < n; j += v[i]) { for (var k = j; k < j + v[i] && k < n; k++) { if (flag && S[k] == '0') count++; if (!flag && S[k] == '1') count++; } flag = (flag == false); } // If current changes required // is less than previous result // then update result if (count < result) result = count; } return result;}// Driver codevar S = "101101";document.write(findMinOperations(S));//This code is contributed by phasing17 |
3
Time Complexity: O(N*sqrt(N)), O(sqrt(N)) to find all divisors and O(N) to find all operations for each divisor.
Auxiliary Space: O(sqrt(N)), for storing all divisors.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
