Dados tres enteros P , Q y R , la tarea es generar una string binaria con pares P, Q y R de caracteres consecutivos con suma 0, 1 y 2 respectivamente.
Ejemplos:
Entrada: P = 1, Q = 2, R = 2
Salida: 111001
Explicación: Las
substrings «00», «10», «01» y «11» tienen sumas 0, 1, 1 y 2 respectivamente.
Por lo tanto, el siguiente conjunto de substrings { {«11»}, {«11»}, {«10»}, {«00»}, {«01»} } satisface las restricciones dadas. Por lo tanto, la string formada por las substrings es 111001.
Entrada: P = 3, Q = 1, R = 0
Salida: 10000
Enfoque: Para resolver este problema, debemos seguir los siguientes pasos:
- Si P y R son distintos de cero , entonces hay al menos un par de caracteres consecutivos con suma 1. Por lo tanto, si Q proporcionado es 0, en tal caso, entonces no se puede formar esa string. Por lo tanto, devuelve -1 .
- Si Q es cero, y solo uno de P y R es distinto de cero, agregue 0 P+1 veces si P no es cero o agregue 1 R+1 vez si R no es cero .
- Si todos ellos son distintos de cero:
- Agregue 0 y 1 P + 1 y Q + 1 veces respectivamente.
- Agregue 0 y 1 alternativamente Q – 1 vez.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to generate a binary
// string with given frequencies
// of sums of consecutive
// pair of characters
#include <bits/stdc++.h>
using namespace std;
// A Function that generates
// and returns the binary string
string build_binary_str(int p,
int q, int r)
{
// P: Frequency of consecutive
// characters with sum 0
// Q: Frequency of consecutive
// characters with sum 1
// R: Frequency of consecutive
// characters with sum 2
string ans = "";
// If no consecutive
// character adds up to 1
if (q == 0) {
// Not possible if both P
// and Q are non - zero
if (p != 0 && r != 0) {
return "-1";
}
else {
// If P is not equal to 0
if (p) {
// Append 0 P + 1 times
ans = string(p + 1, '0');
}
else {
// Append 1 R + 1 times
ans = string(r + 1, '1');
}
}
}
else {
// Append "01" to satisfy Q
for (int i = 1; i <= q + 1; i++) {
if (i % 2 == 0) {
ans += '0';
}
else {
ans += '1';
}
}
// Append "0" P times
ans.insert(1, string(p, '0'));
// Append "1" R times
ans.insert(0, string(r, '1'));
}
return ans;
}
// Driver Code
int main()
{
int p = 1, q = 2, r = 2;
cout << build_binary_str(p, q, r);
return 0;
}
Java
// Java program to generate a binary
// String with given frequencies
// of sums of consecutive
// pair of characters
class GFG{
// A Function that generates
// and returns the binary String
static String build_binary_str(int p,
int q, int r)
{
// P: Frequency of consecutive
// characters with sum 0
// Q: Frequency of consecutive
// characters with sum 1
// R: Frequency of consecutive
// characters with sum 2
String ans = "";
// If no consecutive
// character adds up to 1
if (q == 0)
{
// Not possible if both P
// and Q are non - zero
if (p != 0 && r != 0)
{
return "-1";
}
else
{
// If P is not equal to 0
if (p > 0)
{
// Append 0 P + 1 times
ans = Strings(p + 1, '0');
}
else
{
// Append 1 R + 1 times
ans = Strings(r + 1, '1');
}
}
}
else
{
// Append "01" to satisfy Q
for (int i = 1; i <= q + 1; i++)
{
if (i % 2 == 0)
{
ans += '0';
}
else
{
ans += '1';
}
}
// Append "0" P times
ans = ans.substring(0, 1) + Strings(p, '0') + ans.substring(1);
// Append "1" R times
ans = Strings(r, '1') + ans;
}
return ans;
}
static String Strings(int p, char c)
{
String ans = "";
for (int i = 0; i < p; i++)
ans += c;
return ans;
}
// Driver Code
public static void main(String[] args)
{
int p = 1, q = 2, r = 2;
System.out.print(build_binary_str(p, q, r));
}
}
// This code is contributed by shikhasingrajput
Python3
# Python3 program to generate a binary # string with given frequencies # of sums of consecutive # pair of characters # A Function that generates # and returns the binary string def build_binary_str(p, q, r): # P: Frequency of consecutive # characters with sum 0 # Q: Frequency of consecutive # characters with sum 1 # R: Frequency of consecutive # characters with sum 2 ans = "" # If no consecutive # character adds up to 1 if (q == 0): # Not possible if both P # and Q are non - zero if (p != 0 and r != 0): return "-1" else: # If P is not equal to 0 if (p): # Append 0 P + 1 times temp = "" for i in range(p + 1): temp += '0' ans = temp else: # Append 1 R + 1 times temp = "" for i in range(r + 1): temp += '1' ans = temp else: # Append "01" to satisfy Q for i in range(1, q + 2): if (i % 2 == 0): ans += '0' else: ans += '1' # Append "0" P times temp = "" for i in range(p): temp += '0' st = "" st += ans[0] st += temp for i in range(1, len(ans)): st += ans[i] ans = st # Append "1" R times temp = "" for i in range(r): temp += '1' ans = temp + ans return ans # Driver Code if __name__ == '__main__': p = 1 q = 2 r = 2 print(build_binary_str(p, q, r)) # This code is contributed by Surendra_Gangwar
C#
// C# program to generate a binary
// String with given frequencies
// of sums of consecutive
// pair of characters
using System;
class GFG{
// A Function that generates
// and returns the binary String
static String build_binary_str(int p,
int q, int r)
{
// P: Frequency of consecutive
// characters with sum 0
// Q: Frequency of consecutive
// characters with sum 1
// R: Frequency of consecutive
// characters with sum 2
String ans = "";
// If no consecutive
// character adds up to 1
if (q == 0)
{
// Not possible if both P
// and Q are non - zero
if (p != 0 && r != 0)
{
return "-1";
}
else
{
// If P is not equal to 0
if (p > 0)
{
// Append 0 P + 1 times
ans = Strings(p + 1, '0');
}
else
{
// Append 1 R + 1 times
ans = Strings(r + 1, '1');
}
}
}
else
{
// Append "01" to satisfy Q
for (int i = 1; i <= q + 1; i++)
{
if (i % 2 == 0)
{
ans += '0';
}
else
{
ans += '1';
}
}
// Append "0" P times
ans = ans.Substring(0, 1) +
Strings(p, '0') +
ans.Substring(1);
// Append "1" R times
ans = Strings(r, '1') + ans;
}
return ans;
}
static String Strings(int p, char c)
{
String ans = "";
for (int i = 0; i < p; i++)
ans += c;
return ans;
}
// Driver Code
public static void Main(String[] args)
{
int p = 1, q = 2, r = 2;
Console.Write(build_binary_str(p,
q, r));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program to generate a binary
// string with given frequencies
// of sums of consecutive
// pair of characters
// A Function that generates
// and returns the binary string
function build_binary_str(p, q, r)
{
// P: Frequency of consecutive
// characters with sum 0
// Q: Frequency of consecutive
// characters with sum 1
// R: Frequency of consecutive
// characters with sum 2
let ans = "";
// If no consecutive
// character adds up to 1
if (q == 0) {
// Not possible if both P
// and Q are non - zero
if (p != 0 && r != 0) {
return "-1";
}
else {
// If P is not equal to 0
if (p) {
// Append 0 P + 1 times
ans = new Array(p + 1, '0');
}
else {
// Append 1 R + 1 times
ans = String(r + 1, '1');
}
}
}
else {
// Append "01" to satisfy Q
for (let i = 1; i <= q + 1; i++) {
if (i % 2 == 0) {
ans += '0';
}
else {
ans += '1';
}
}
// Append "0" P times
ans = ans.substr(0, 1) + Strings(p, '0') + ans.substr(1);
// Append "1" R times
ans = Strings(r, '1') + ans;
}
return ans;
}
function Strings(p, c)
{
let ans = "";
for (let i = 0; i < p; i++)
ans += c;
return ans;
}
// Driver Code
let p = 1, q = 2, r = 2;
document.write(build_binary_str(p, q, r));
// This code is contributed by _saurabh_jaiswal.
</script>
Producción:
111001
Complejidad temporal: O(P + Q + R)