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:
- 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