Genere una string binaria sin 0 consecutivos y como máximo K 1 consecutivos

Dados dos números enteros N y M , la tarea es construir una string binaria con las siguientes condiciones: 

  • La string binaria consta de N 0 y M 1
  • La string binaria tiene como máximo K 1 consecutivos.
  • La string binaria no contiene ningún 0 adyacente.

Si no es posible construir una string binaria de este tipo, imprima -1 .

Ejemplos: 
 

Entrada: N = 5, M = 9, K = 2 
Salida: 01101101101101 
Explicación: 
La string “01101101101101” cumple las siguientes condiciones: 
 

  • No hay 0 consecutivos presentes.
  • No hay más de K(= 2) 1 consecutivos presentes.

Entrada: N = 4, M = 18, K = 4 
Salida: 1101111011110111101111 
 

Acercarse:  

Para construir una string binaria que satisfaga las propiedades dadas, observe lo siguiente:

  • Para que no haya dos ‘ 0consecutivos , debe haber al menos un ‘ 1 ‘ entre ellos.
  • Por lo tanto, para un número N de ‘ 0 ‘, debe haber al menos N-11 ‘ presentes para que se genere una string del tipo requerido.
  • Dado que no se pueden colocar juntos más de K ‘ 1 ‘ consecutivos , para N 0 , puede haber un máximo de (N+1) * K ‘1 ‘ posibles.
  • Por lo tanto, el número de ‘ 1 ‘ debe estar dentro del rango: 
     

 
 

n-1? ¿M? (N + 1) * K 
 

 

  • Si los valores dados N y M no satisfacen la condición anterior, imprima -1 .
  • De lo contrario, siga los pasos a continuación para resolver el problema:
    • Agregue ‘ 0 ‘ a la string final.
    • Inserte ‘ 1 ‘ entre cada par de ‘ 0′ s. Reste N – 1 de M , ya que ya se han colocado N – 11 ‘s.
    • Para los ‘ 1 ‘ restantes , coloque min(K – 1, M)1 ‘ junto a cada ‘ 1 ‘ ya colocado, para asegurarse de que no se coloquen más de K ‘1 juntos.
    • Para los ‘ 1 ‘ restantes , agréguelos al principio y al final de la string final.
  • Finalmente, imprima la string generada.

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

C++

// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to construct the binary string
string ConstructBinaryString(int N, int M,
                             int K)
{
    // Conditions when string construction
    // is not possible
    if (M < (N - 1) || M > K * (N + 1))
        return "-1";
 
    string ans = "";
 
    // Stores maximum 1's that
    // can be placed in between
    int l = min(K, M / (N - 1));
    int temp = N;
    while (temp--) {
        // Place 0's
        ans += '0';
 
        if (temp == 0)
            break;
 
        // Place 1's in between
        for (int i = 0; i < l; i++) {
            ans += '1';
        }
    }
 
    // Count remaining M's
    M -= (N - 1) * l;
 
    if (M == 0)
        return ans;
 
    l = min(M, K);
    // Place 1's at the end
    for (int i = 0; i < l; i++)
        ans += '1';
 
    M -= l;
    // Place 1's at the beginning
    while (M > 0) {
        ans = '1' + ans;
        M--;
    }
 
    // Return the final string
    return ans;
}
 
// Driver Code
int main()
{
    int N = 5, M = 9, K = 2;
 
    cout << ConstructBinaryString(N, M, K);
}

Java

// Java implementation of
// the above approach
class GFG{
     
// Function to construct the binary string
static String ConstructBinaryString(int N, int M,
                                    int K)
{
     
    // Conditions when string construction
    // is not possible
    if (M < (N - 1) || M > K * (N + 1))
        return "-1";
 
    String ans = "";
 
    // Stores maximum 1's that
    // can be placed in between
    int l = Math.min(K, M / (N - 1));
    int temp = N;
     
    while (temp != 0)
    {
        temp--;
         
        // Place 0's
        ans += '0';
 
        if (temp == 0)
            break;
 
        // Place 1's in between
        for(int i = 0; i < l; i++)
        {
            ans += '1';
        }
    }
 
    // Count remaining M's
    M -= (N - 1) * l;
 
    if (M == 0)
        return ans;
 
    l = Math.min(M, K);
     
    // Place 1's at the end
    for(int i = 0; i < l; i++)
        ans += '1';
 
    M -= l;
     
    // Place 1's at the beginning
    while (M > 0)
    {
        ans = '1' + ans;
        M--;
    }
 
    // Return the final string
    return ans;
}
 
// Driver code   
public static void main(String[] args)
{
    int N = 5, M = 9, K = 2;
     
    System.out.println(ConstructBinaryString(N, M, K));
}
}
 
// This code is contributed by rutvik_56

Python3

# Python3 implementation of
# the above approach
 
# Function to construct the binary string
def ConstructBinaryString(N, M, K):
 
    # Conditions when string construction
    # is not possible
    if(M < (N - 1) or M > K * (N + 1)):
        return '-1'
 
    ans = ""
 
    # Stores maximum 1's that
    # can be placed in between
    l = min(K, M // (N - 1))
    temp = N
     
    while(temp):
        temp -= 1
 
        # Place 0's
        ans += '0'
 
        if(temp == 0):
            break
 
        # Place 1's in between
        for i in range(l):
            ans += '1'
 
    # Count remaining M's
    M -= (N - 1) * l
 
    if(M == 0):
        return ans
 
    l = min(M, K)
     
    # Place 1's at the end
    for i in range(l):
        ans += '1'
 
    M -= l
     
    # Place 1's at the beginning
    while(M > 0):
        ans = '1' + ans
        M -= 1
 
    # Return the final string
    return ans
 
# Driver Code
if __name__ == '__main__':
 
    N = 5
    M = 9
    K = 2
     
    print(ConstructBinaryString(N, M , K))
 
# This code is contributed by Shivam Singh

C#

// C# implementation of
// the above approach
using System;
class GFG{
      
// Function to construct the binary string
static String ConstructBinaryString(int N, int M,
                                    int K)
{
      
    // Conditions when string construction
    // is not possible
    if (M < (N - 1) || M > K * (N + 1))
        return "-1";
  
    string ans = "";
  
    // Stores maximum 1's that
    // can be placed in between
    int l = Math.Min(K, M / (N - 1));
    int temp = N;
      
    while (temp != 0)
    {
        temp--;
          
        // Place 0's
        ans += '0';
  
        if (temp == 0)
            break;
  
        // Place 1's in between
        for(int i = 0; i < l; i++)
        {
            ans += '1';
        }
    }
  
    // Count remaining M's
    M -= (N - 1) * l;
  
    if (M == 0)
        return ans;
  
    l = Math.Min(M, K);
      
    // Place 1's at the end
    for(int i = 0; i < l; i++)
        ans += '1';
  
    M -= l;
      
    // Place 1's at the beginning
    while (M > 0)
    {
        ans = '1' + ans;
        M--;
    }
  
    // Return the final string
    return ans;
}
  
// Driver code   
public static void Main(string[] args)
{
    int N = 5, M = 9, K = 2;
      
    Console.Write(ConstructBinaryString(N, M, K));
}
}
  
// This code is contributed by Ritik Bansal

Javascript

<script>
// JavaScript program for the above approach
 
// Function to construct the binary string
function ConstructBinaryString(N, M, K)
{
      
    // Conditions when string construction
    // is not possible
    if (M < (N - 1) || M > K * (N + 1))
        return "-1";
  
    let ans = "";
  
    // Stores maximum 1's that
    // can be placed in between
    let l = Math.min(K, M / (N - 1));
    let temp = N;
      
    while (temp != 0)
    {
        temp--;
          
        // Place 0's
        ans += '0';
  
        if (temp == 0)
            break;
  
        // Place 1's in between
        for(let i = 0; i < l; i++)
        {
            ans += '1';
        }
    }
  
    // Count remaining M's
    M -= (N - 1) * l;
  
    if (M == 0)
        return ans;
  
    l = Math.min(M, K);
      
    // Place 1's at the end
    for(let i = 0; i < l; i++)
        ans += '1';
  
    M -= l;
      
    // Place 1's at the beginning
    while (M > 0)
    {
        ans = '1' + ans;
        M--;
    }
  
    // Return the final string
    return ans;
}
 
// Driver Code   
     
        let N = 5, M = 9, K = 2;
      
    document.write(ConstructBinaryString(N, M, K));
                     
</script>
Producción: 

01101101101101

 

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

Publicación traducida automáticamente

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