Dados n y k, construya un palíndromo de tamaño n usando un número binario de tamaño k repitiéndose para envolver el palíndromo. El palíndromo siempre debe comenzar con 1 y contiene un número máximo de ceros.
Ejemplos:
Input : n = 5, k = 3 Output : 11011 Explanation : the 3 sized substring is 110 combined twice and trimming the extra 0 in the end to give 11011. Input : n = 2, k = 8 Output : 11 Explanation : the 8 sized substring is 11...... wrapped to two places to give 11.
El enfoque ingenuo sería probar cada palíndromo de tamaño k comenzando con 1 de modo que se forme un palíndromo de tamaño n. Este enfoque tiene una complejidad exponencial.
Una mejor manera de hacer esto es inicializar el número binario de tamaño k con el índice y conectar el palíndromo de la forma en que debería ser. Como el último carácter del palíndromo debe coincidir con el primero, busque qué índices estarán presentes en esas ubicaciones y vincúlelos. Establezca cada carácter vinculado con el índice 0 en 1 y la string estará lista. Este enfoque tendrá una complejidad lineal.
En este enfoque, primero coloque el índice del binario de tamaño k para mantenerlo en una array, por ejemplo, si n = 7, k = 3 arr se convierte en [0, 1, 2, 0, 1, 2, 0]. A continuación, en el gráfico de connectchars, conecte los índices del binario de tamaño k, que debería ser el mismo pasando por la propiedad del palíndromo, que es kth y (n – k – 1)th variable debería ser la misma, de modo que 0 esté vinculado a 1 (y viceversa), 1 está vinculado a 2 (y viceversa) y así sucesivamente. Después de eso, verifique qué está vinculado con 0 en la array connectchars y haga que todos los índices asociados sean uno (porque el primer número debe ser distinto de cero) utilizando el enfoque dfs. En el dfs, pase 0, la string de respuesta final y el gráfico. Comience por hacer que el padre sea 1 y verifique si sus hijos son cero, si los hacen a ellos y a sus hijos 1. Esto hace que solo los índices requeridos de la string de tamaño k sean uno, otros se dejan cero. Finalmente, la respuesta contiene los índices 0 a k – 1 y se imprimen los dígitos correspondientes a arr.
C++
// CPP code to form binary palindrome
#include <iostream>
#include <vector>
using namespace std;
// function to apply DFS
void dfs(int parent, int ans[], vector<int> connectchars[])
{
// set the parent marked
ans[parent] = 1;
// if the node has not been visited set it and
// its children marked
for (int i = 0; i < connectchars[parent].size(); i++) {
if (!ans[connectchars[parent][i]])
dfs(connectchars[parent][i], ans, connectchars);
}
}
void printBinaryPalindrome(int n, int k)
{
int arr[n], ans[n] = { 0 };
// link which digits must be equal
vector<int> connectchars[k];
for (int i = 0; i < n; i++)
arr[i] = i % k;
// connect the two indices
for (int i = 0; i < n / 2; i++) {
connectchars[arr[i]].push_back(arr[n - i - 1]);
connectchars[arr[n - i - 1]].push_back(arr[i]);
}
// set everything connected to
// first character as 1
dfs(0, ans, connectchars);
for (int i = 0; i < n; i++)
cout << ans[arr[i]];
}
// driver code
int main()
{
int n = 10, k = 4;
printBinaryPalindrome(n, k);
return 0;
}
Java
// JAVA code to form binary palindrome
import java.util.*;
class GFG
{
// function to apply DFS
static void dfs(int parent, int ans[],
Vector<Integer> connectchars[])
{
// set the parent marked
ans[parent] = 1;
// if the node has not been visited set it and
// its children marked
for (int i = 0; i < connectchars[parent].size(); i++)
{
if (ans[connectchars[parent].get(i)] != 1)
dfs(connectchars[parent].get(i), ans, connectchars);
}
}
static void printBinaryPalindrome(int n, int k)
{
int []arr = new int[n];
int []ans = new int[n];
// link which digits must be equal
Vector<Integer> []connectchars = new Vector[k];
for (int i = 0; i < k; i++)
connectchars[i] = new Vector<Integer>();
for (int i = 0; i < n; i++)
arr[i] = i % k;
// connect the two indices
for (int i = 0; i < n / 2; i++)
{
connectchars[arr[i]].add(arr[n - i - 1]);
connectchars[arr[n - i - 1]].add(arr[i]);
}
// set everything connected to
// first character as 1
dfs(0, ans, connectchars);
for (int i = 0; i < n; i++)
System.out.print(ans[arr[i]]);
}
// Driver code
public static void main(String[] args)
{
int n = 10, k = 4;
printBinaryPalindrome(n, k);
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 code to form binary palindrome # function to apply DFS def dfs(parent, ans, connectchars): # set the parent marked ans[parent] = 1 # if the node has not been visited # set it and its children marked for i in range(len(connectchars[parent])): if (not ans[connectchars[parent][i]]): dfs(connectchars[parent][i], ans, connectchars) def printBinaryPalindrome(n, k): arr = [0] * n ans = [0] * n # link which digits must be equal connectchars = [[] for i in range(k)] for i in range(n): arr[i] = i % k # connect the two indices for i in range(int(n / 2)): connectchars[arr[i]].append(arr[n - i - 1]) connectchars[arr[n - i - 1]].append(arr[i]) # set everything connected to # first character as 1 dfs(0, ans, connectchars) for i in range(n): print(ans[arr[i]], end = "") # Driver Code if __name__ == '__main__': n = 10 k = 4 printBinaryPalindrome(n, k) # This code is contributed by PranchalK
C#
// C# code to form binary palindrome
using System;
using System.Collections.Generic;
class GFG
{
// function to apply DFS
static void dfs(int parent, int []ans,
List<int> []connectchars)
{
// set the parent marked
ans[parent] = 1;
// if the node has not been visited set it and
// its children marked
for (int i = 0; i < connectchars[parent].Count; i++)
{
if (ans[connectchars[parent][i]] != 1)
dfs(connectchars[parent][i], ans, connectchars);
}
}
static void printBinaryPalindrome(int n, int k)
{
int []arr = new int[n];
int []ans = new int[n];
// link which digits must be equal
List<int> []connectchars = new List<int>[k];
for (int i = 0; i < k; i++)
connectchars[i] = new List<int>();
for (int i = 0; i < n; i++)
arr[i] = i % k;
// connect the two indices
for (int i = 0; i < n / 2; i++)
{
connectchars[arr[i]].Add(arr[n - i - 1]);
connectchars[arr[n - i - 1]].Add(arr[i]);
}
// set everything connected to
// first character as 1
dfs(0, ans, connectchars);
for (int i = 0; i < n; i++)
Console.Write(ans[arr[i]]);
}
// Driver code
public static void Main(String[] args)
{
int n = 10, k = 4;
printBinaryPalindrome(n, k);
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript code to form binary palindrome
// function to apply DFS
function dfs(parent, ans, connectchars) {
// set the parent marked
ans[parent] = 1;
// if the node has not been visited set it and
// its children marked
for (let i = 0; i < connectchars[parent].length; i++) {
if (!ans[connectchars[parent][i]])
dfs(connectchars[parent][i], ans, connectchars);
}
}
function printBinaryPalindrome(n, k) {
let arr = new Array(n), ans = new Array(n).fill(0);
// link which digits must be equal
let connectchars = new Array(k).fill(0).map(() => new Array(k).fill(0));
for (let i = 0; i < n; i++)
arr[i] = i % k;
// connect the two indices
for (let i = 0; i < n / 2; i++) {
connectchars[arr[i]].push(arr[n - i - 1]);
connectchars[arr[n - i - 1]].push(arr[i]);
}
// set everything connected to
// first character as 1
dfs(0, ans, connectchars);
for (let i = 0; i < n; i++)
document.write(ans[arr[i]]);
}
// driver code
let n = 10, k = 4;
printBinaryPalindrome(n, k);
// This code is contributed by gfgking.
</script>
1100110011
Complejidad de tiempo : O(n)