La string binaria lexicográficamente más pequeña formada al cambiar bits en índices no divisibles K1 o K2, de modo que el recuento de 1 siempre es mayor que 0 desde la izquierda

Dada una string binaria S (indexación basada en 1) de tamaño N y dos números enteros positivos K1 y K2 , la tarea es encontrar la string lexicográficamente más pequeña cambiando los caracteres en índices que no son divisibles por K1 o K2 de modo que el cuenta de 1s hasta que cada índice posible sea siempre mayor que la cuenta de 0s . Si no es posible formar tal string, la impresión “-1” .

Ejemplos:

Entrada: K1 = 4, K2 = 6, S = “0000”
Salida: 1110
Explicación:
Dado que el índice 4 es divisible por K1(= 4). Entonces, sin invertir ese índice, la string se modifica a «1110», que es lexicográficamente la más pequeña entre todas las combinaciones posibles de cambios.

Entrada: K1 = 2, K2 = 4, S = “11000100”
Salida: 11100110

Enfoque: el problema se puede resolver modificando la string S de izquierda a derecha para cada posición desbloqueada, si es posible hacer 0 , luego convertirlo en 0 ; de lo contrario, convertirlo en 1 . Siga los pasos a continuación para resolver el problema:

  • Inicialice dos variables, digamos c1 y c0 para almacenar el recuento de 1 y 0 respectivamente.
  • Inicialice un vector, digamos pos[], que almacena las posiciones de todos los 0 que no son divisibles por K1 o K2 .
  • Atraviese la string S dada y realice los siguientes pasos:
    • Si el carácter es 0 , incremente el valor de c0 . De lo contrario, incremente el valor de c1 .
    • Si el índice actual no es divisible por K1 o K2 , inserte este índice en el vector pos[] .
    • Si en cualquier índice i , el recuento de 0 se vuelve mayor o igual a 1 , entonces:
      • Si el vector está vacío, la string no se puede modificar a la combinación requerida. Por lo tanto, imprima -1 .
      • De lo contrario, saque la última posición presente en el vector y actualice el valor de c0 como c0 – 1 y c1 como c1 + 1 y S[pos] = ‘1’ .
  • Después de completar los pasos anteriores, imprima la string S la string modificada.

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

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find lexicographically
// smallest string having number of 1s
// greater than number of 0s
void generateString(int k1, int k2, string s)
{
    // C1s And C0s stores the count of
    // 1s and 0s at every position
    int C1s = 0, C0s = 0;
    int flag = 0;
    vector<int> pos;
 
    // Traverse the string S
    for (int i = 0; i < s.length(); i++) {
 
        if (s[i] == '0') {
            C0s++;
 
            // If the position is not
            // divisible by k1 and k2
            if ((i + 1) % k1 != 0
                && (i + 1) % k2 != 0) {
                pos.push_back(i);
            }
        }
 
        else {
            C1s++;
        }
 
        if (C0s >= C1s) {
 
            // If C0s >= C1s and pos[] is
            // empty then the string can't
            // be formed
            if (pos.size() == 0) {
                cout << -1;
                flag = 1;
                break;
            }
 
            // If pos[] is not empty then
            // flip the bit of last position
            // present in pos[]
            else {
                int k = pos.back();
                s[k] = '1';
                C0s--;
                C1s++;
                pos.pop_back();
            }
        }
    }
 
    // Print the result
    if (flag == 0) {
        cout << s;
    }
}
 
// Driver Code
int main()
{
    int K1 = 2, K2 = 4;
    string S = "11000100";
    generateString(K1, K2, S);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG
{
 
// Function to find lexicographically
// smallest String having number of 1s
// greater than number of 0s
static void generateString(int k1, int k2, char[] s)
{
   
    // C1s And C0s stores the count of
    // 1s and 0s at every position
    int C1s = 0, C0s = 0;
    int flag = 0;
    Vector<Integer> pos = new Vector<Integer>();
 
    // Traverse the String S
    for (int i = 0; i < s.length; i++) {
 
        if (s[i] == '0') {
            C0s++;
 
            // If the position is not
            // divisible by k1 and k2
            if ((i + 1) % k1 != 0
                && (i + 1) % k2 != 0) {
                pos.add(i);
            }
        }
 
        else {
            C1s++;
        }
 
        if (C0s >= C1s) {
 
            // If C0s >= C1s and pos[] is
            // empty then the String can't
            // be formed
            if (pos.size() == 0) {
                System.out.print(-1);
                flag = 1;
                break;
            }
 
            // If pos[] is not empty then
            // flip the bit of last position
            // present in pos[]
            else {
                int k = pos.get(pos.size()-1);
                s[k] = '1';
                C0s--;
                C1s++;
                pos.remove(pos.size() - 1);
            }
        }
    }
 
    // Print the result
    if (flag == 0) {
        System.out.print(s);
    }
}
 
// Driver Code
public static void main(String[] args)
{
    int K1 = 2, K2 = 4;
    String S = "11000100";
    generateString(K1, K2, S.toCharArray());
 
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python 3 program for the above approach
 
# Function to find lexicographically
# smallest string having number of 1s
# greater than number of 0s
def generateString(k1, k2, s):
   
    # C1s And C0s stores the count of
    # 1s and 0s at every position
    s = list(s)
    C1s = 0
    C0s = 0
    flag = 0
    pos = []
 
    # Traverse the string S
    for i in range(len(s)):
        if (s[i] == '0'):
            C0s += 1
 
            # If the position is not
            # divisible by k1 and k2
            if ((i + 1) % k1 != 0 and (i + 1) % k2 != 0):
                pos.append(i)
 
        else:
            C1s += 1
 
        if (C0s >= C1s):
            # If C0s >= C1s and pos[] is
            # empty then the string can't
            # be formed
            if (len(pos) == 0):
                print(-1)
                flag = 1
                break
 
            # If pos[] is not empty then
            # flip the bit of last position
            # present in pos[]
            else:
                k = pos[len(pos)-1]
                s[k] = '1'
                C0s -= 1
                C1s += 1
                pos = pos[:-1]
 
    # Print the result
    s = ''.join(s)
    if (flag == 0):
        print(s)
 
# Driver Code
if __name__ == '__main__':
    K1 = 2
    K2 = 4
    S = "11000100"
    generateString(K1, K2, S)
     
    # This code is contributed by SURENDRA_GANGWAR.

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG {
 
// Function to find lexicographically
// smallest String having number of 1s
// greater than number of 0s
static void generateString(int k1, int k2, char[] s)
{
    
    // C1s And C0s stores the count of
    // 1s and 0s at every position
    int C1s = 0, C0s = 0;
    int flag = 0;
    List<int> pos = new List<int>();
  
    // Traverse the String S
    for (int i = 0; i < s.Length; i++) {
  
        if (s[i] == '0') {
            C0s++;
  
            // If the position is not
            // divisible by k1 and k2
            if ((i + 1) % k1 != 0
                && (i + 1) % k2 != 0) {
                pos.Add(i);
            }
        }
  
        else {
            C1s++;
        }
  
        if (C0s >= C1s) {
  
            // If C0s >= C1s and pos[] is
            // empty then the String can't
            // be formed
            if (pos.Count == 0) {
                Console.WriteLine(-1);
                flag = 1;
                break;
            }
  
            // If pos[] is not empty then
            // flip the bit of last position
            // present in pos[]
            else {
                int k = pos[(pos.Count - 1)];
                s[k] = '1';
                C0s--;
                C1s++;
                pos.Remove(pos.Count - 1);
            }
        }
    }
  
    // Print the result
    if (flag == 0) {
        Console.WriteLine(s);
    }
}
 
    // Driver Code
    public static void Main()
    {
    int K1 = 2, K2 = 4;
    string S = "11000100";
    generateString(K1, K2, S.ToCharArray());
    }
}
 
// This code is contributed by avijitmondal1998.

Javascript

<script>
        // JavaScript Program to implement
        // the above approach
 
        // Function to find lexicographically
        // smallest string having number of 1s
        // greater than number of 0s
        function generateString(k1, k2, s)
        {
         
            // C1s And C0s stores the count of
            // 1s and 0s at every position
            let C1s = 0, C0s = 0;
            let flag = 0;
            let pos = [];
 
            // Traverse the string S
            for (let i = 0; i < s.length; i++) {
 
                if (s[i] == '0') {
                    C0s++;
 
                    // If the position is not
                    // divisible by k1 and k2
                    if ((i + 1) % k1 != 0
                        && (i + 1) % k2 != 0) {
                        pos.push(i);
                    }
                }
 
                else {
                    C1s++;
                }
 
                if (C0s >= C1s) {
 
                    // If C0s >= C1s and pos[] is
                    // empty then the string can't
                    // be formed
                    if (pos.length == 0) {
                        cout << -1;
                        flag = 1;
                        break;
                    }
 
                    // If pos[] is not empty then
                    // flip the bit of last position
                    // present in pos[]
                    else {
                        let k = pos[pos.length - 1];
                        var ns = s.replace(s[k], '1');
                        C0s--;
                        C1s++;
                        pos.pop();
                    }
                }
            }
 
            // Print the result
            if (flag == 0) {
                document.write(ns);
            }
        }
 
        // Driver Code
        let K1 = 2, K2 = 4;
        let S = "11000100";
        generateString(K1, K2, S);
 
// This code is contributed by Potta Lokesh
 
    </script>
Producción: 

11100110

 

Complejidad temporal: O(N)
Espacio auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por tejasdhanait 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 *