Dada una string binaria S de longitud N y un entero positivo M , la tarea es verificar si es posible rotar la string circularmente cualquier número de veces de modo que cualquier par de 1 consecutivos estén separados por M 0 como máximo . Si es posible, escriba «Sí» . De lo contrario, escriba “No” .
Ejemplos:
Entrada: S = “101001”, M = 1
Salida: Sí
Explicación: Desplace hacia la derecha los caracteres de la string dada en 1 lugar. Por lo tanto, la string S se modifica a “110100”, dejando todos los pares de 1 consecutivos separados como máximo por M(= 1) 0 s.Entrada: S = 1001001, M = 1
Salida: No
Enfoque: El problema dado se puede resolver basándose en la observación de que si hay más de 1 par de 1 adyacentes que tienen más de M números de 0 entre ellos, entonces no es posible satisfacer la condición dada, porque solo ese par puede ser maneja girando la cuerda de tal manera que todos los 0 entre ellos estén al final.
Siga los pasos a continuación para resolver el problema:
- Inicialice un vector , digamos V , para almacenar los índices de todos los 1 en la string S dada .
- Inicialice una variable, digamos count , para almacenar el número de pares de 1 que tengan más de M 0 entre ellos.
- Recorre la string S dada y almacena todos los índices de ‘1’ en el vector V .
- Recorra el vector V , comenzando desde el índice 1 usando una variable, digamos i , y realice los siguientes pasos:
- Almacene el número de ceros entre los índices V[i] y V[i – 1] en la string S en una variable T como (V[i] – V[i – 1] – 1) .
- Si el valor de T es mayor que M , incremente el valor de count en 1 .
- Si el número de 0 entre la primera y la última aparición de ‘1’ es mayor que M , incremente el valor de count en 1 .
- Después de completar los pasos anteriores, si el valor de count es como máximo 1 , imprima Sí . De lo contrario, escriba “No” .
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 check if any pair of
// consecutive 1s can be separated by at
// most M 0s by circular rotation of string S
void rotateString(int n, int m, string s)
{
// Stores the indices of all 1s
vector<int> v;
// Store the number of pairs
// separated by at least M 0s
int cnt = 0;
// Traverse the string
for (int i = 0; i < n; i++) {
if (s[i] == '1') {
// Store the current index
v.push_back(i);
}
}
// Traverse the array containing indices
for (int i = 1; i < (int)v.size(); i++) {
// If the number of 0s > M,
// then increment cnt by 1
if ((v[i] - v[i - 1] - 1) > m) {
// Increment cnt
cnt++;
}
}
// Check if at least M '0's lie between
// the first and last occurrence of '1'
if (v.size() >= 2
&& (n - (v.back() - v[0]) - 1) > m) {
// Increment cnt
cnt++;
}
// If the value of cnt <= 1, then
// rotation of string is possible
if (cnt <= 1) {
cout << "Yes";
}
// Otherwise
else {
cout << "No";
}
}
// Driver Code
int main()
{
string S = "101001";
int M = 1;
int N = S.size();
rotateString(N, M, S);
return 0;
}
Java
// Java program for the above approach
class GFG{
// Function to check if any pair of
// consecutive 1s can be separated by at
// most M 0s by circular rotation of string S
static void rotateString(int n, int m, String s)
{
// Stores the indices of all 1s
int v[] = new int[n];
// Store the number of pairs
// separated by at least M 0s
int cnt = 0;
int j = 0;
// Traverse the string
for(int i = 0; i < n; i++)
{
if (s.charAt(i) == '1')
{
// Store the current index
v[j] = i;
j += 1;
}
}
// Traverse the array containing indices
for(int i = 1; i < j; i++)
{
// If the number of 0s > M,
// then increment cnt by 1
if ((v[i] - v[i - 1] - 1) > m)
{
// Increment cnt
cnt++;
}
}
// Check if at least M '0's lie between
// the first and last occurrence of '1'
if (j >= 2 && (n - (v[j - 1] - v[0]) - 1) > m)
{
// Increment cnt
cnt++;
}
// If the value of cnt <= 1, then
// rotation of string is possible
if (cnt <= 1)
{
System.out.print("Yes");
}
// Otherwise
else
{
System.out.print("No");
}
}
// Driver Code
public static void main (String[] args)
{
String S = "101001";
int M = 1;
int N = S.length();
rotateString(N, M, S);
}
}
// This code is contributed by AnkThon
Python3
# Python3 program for the above approach
# Function to check if any pair of
# consecutive 1s can be separated by at
# most M 0s by circular rotation of string S
def rotateString(n, m, s):
# Stores the indices of all 1s
v = []
# Store the number of pairs
# separated by at least M 0s
cnt = 0
# Traverse the string
for i in range(n):
if (s[i] == '1'):
# Store the current index
v.append(i)
# Traverse the array containing indices
for i in range(1, len(v)):
# If the number of 0s > M,
# then increment cnt by 1
if ((v[i] - v[i - 1] - 1) > m):
# Increment cnt
cnt += 1
# Check if at least M '0's lie between
# the first and last occurrence of '1'
if (len(v) >= 2 and
(n - (v[-1] - v[0]) - 1) > m):
# Increment cnt
cnt += 1
# If the value of cnt <= 1, then
# rotation of string is possible
if (cnt <= 1):
print("Yes")
# Otherwise
else:
print("No")
# Driver Code
if __name__ == '__main__':
S = "101001"
M = 1
N = len(S)
rotateString(N, M, S)
# This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to check if any pair of
// consecutive 1s can be separated by at
// most M 0s by circular rotation of string S
static void rotateString(int n, int m, string s)
{
// Stores the indices of all 1s
List<int> v = new List<int>();
// Store the number of pairs
// separated by at least M 0s
int cnt = 0;
// Traverse the string
for(int i = 0; i < n; i++)
{
if (s[i] == '1')
{
// Store the current index
v.Add(i);
}
}
// Traverse the array containing indices
for(int i = 1; i < v.Count; i++)
{
// If the number of 0s > M,
// then increment cnt by 1
if ((v[i] - v[i - 1] - 1) > m)
{
// Increment cnt
cnt++;
}
}
// Check if at least M '0's lie between
// the first and last occurrence of '1'
if (v.Count >= 2 &&
(n - (v[v.Count - 1] - v[0]) - 1) > m)
{
// Increment cnt
cnt++;
}
// If the value of cnt <= 1, then
// rotation of string is possible
if (cnt <= 1)
{
Console.Write("Yes");
}
// Otherwise
else
{
Console.Write("No");
}
}
// Driver Code
public static void Main()
{
string S = "101001";
int M = 1;
int N = S.Length;
rotateString(N, M, S);
}
}
// This code is contributed by ipg2016107
Javascript
<script>
// Javascript program for the above approach
// Function to check if any pair of
// consecutive 1s can be separated by at
// most M 0s by circular rotation of string S
function rotateString(n, m, s)
{
// Stores the indices of all 1s
var v = [];
// Store the number of pairs
// separated by at least M 0s
var cnt = 0;
var i;
// Traverse the string
for (i = 0; i < n; i++) {
if (s[i] == '1') {
// Store the current index
v.push(i);
}
}
// Traverse the array containing indices
for (i = 1; i < v.length; i++) {
// If the number of 0s > M,
// then increment cnt by 1
if ((v[i] - v[i - 1] - 1) > m) {
// Increment cnt
cnt++;
}
}
// Check if at least M '0's lie between
// the first and last occurrence of '1'
if (v.length >= 2
&& (n - (v[v.length-1] - v[0]) - 1) > m) {
// Increment cnt
cnt++;
}
// If the value of cnt <= 1, then
// rotation of string is possible
if (cnt <= 1) {
document.write("Yes");
}
// Otherwise
else {
document.write("No");
}
}
// Driver Code
var S = "101001";
var M = 1;
var N = S.length;
rotateString(N, M, S);
</script>
Producción:
Yes
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por shreyajaiswal3 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA