Minimice los cambios para hacer que las substrings de tamaño K sean iguales y alternativas

Posted on by Rudeus Greyrat

Dada una string binaria S de longitud N , la tarea es minimizar el número de operaciones necesarias para encontrar una string binaria T de la misma longitud N tal que:

  • En una sola operación, se permite voltear cualquier bit , es decir, convertir 0 a 1 o viceversa.
  • En la string binaria T , elija un número K , tal que: 
    • N es perfectamente divisible por K , y
    • Los primeros K bits en T son 0 , los siguientes K son 1 , los siguientes K son 0 , y así sucesivamente.

Ejemplos: 

Entrada: S = 1011011
Salida: 4
Explicación: 
Si elegimos K = 1, entonces la string requerida S=0101010, Movimientos requeridos 4
Si elegimos K = 7, entonces la string requerida S=0000000, Movimientos requeridos 5
Valores de K= 2, 3, 4, 5, 6 no está permitido porque no se divide perfectamente N = 7.
Elija K = 1. Entonces, la string final es 0101010, invierta el primer, segundo, tercer y séptimo bit. Imprime 4 porque la string S satisface todas las condiciones después de realizar 4 movimientos.

Entrada: S = 000001
Salida: 1
Explicación: 
Si elegimos K=1, entonces la string requerida S=010101, Movimientos requeridos 2
Si elegimos K=2, entonces la string requerida S=001100, Movimientos requeridos 3
Si elegimos K=3 , entonces string requerida S=000111, Movimientos requeridos 2
Si elegimos K=6, entonces string requerida S=000000, Movimientos requeridos 1
Entonces, Seleccione K=6, Entonces, la salida será 1.

 

Enfoque: El enfoque se basa en la siguiente observación:

En el enunciado del problema se menciona que tenemos que elegir K tal que N sea divisible por K, de modo que podamos dividir nuestro problema en subproblemas para encontrar todos los divisores de N y luego encontrar el número de operaciones requeridas para cada uno de los divisores y elegir el número mínimo de operación entre todos ellos.

Con base en la observación anterior, siga los pasos a continuación para implementar este enfoque:

  • Encuentre todos los divisores de N (tamaño de la string dada).
  • Para cada divisor, Traverse the String y para cada iteración: 
    • Cuente el número de cambios requeridos en la string dada si elegimos el K = divisor actual.
    • Si los cambios actuales requeridos son menores que el resultado anterior, actualícelo con el resultado actual. 
  • Devolver los cambios mínimos requeridos.

A continuación se muestra la implementación del enfoque anterior:

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 K
int 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 code
int main()
{
    string S = "101101";
    cout << findMinOperations(S);
    return 0;
}

Java

// Java code to implement above approach
 
import 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 n
 
 
def 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 K
 
 
def 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 Code
S = "101101"
print(findMinOperations(S))
 
# this code was contributed by phasing17

C#

// C# code to implement above approach
using 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 K
function 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 code
var S = "101101";
document.write(findMinOperations(S));
 
//This code is contributed by phasing17
Producción

3

Complejidad de tiempo: O(N*sqrt(N)), O(sqrt(N)) para encontrar todos los divisores y O(N) para encontrar todas las operaciones para cada divisor.
Espacio auxiliar: O(sqrt(N)), para almacenar todos los divisores.

Publicación traducida automáticamente

Artículo escrito por khatriharsh281 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *