# Construct binary palindrome by repeated appending and trimming

I was reading an article on Construct binary palindrome by repeated appending and trimming. The problem is Given n and k, Construct a palindrome of size n using a binary number of size k repeating itself to wrap into the palindrome. The palindrome must always begin with 1 and contains maximum number of zeros.

I solved the problem using this algorithm-

1. I will declare a string of size n with all the entries 0.
2. Leftmost character has to be 1, so to be a palindrome rightmost should also be a 1 .
3. Now after every k-1 places starting from start, I will put a 1.
4. And before every k-1 places starting from end, I will put a 1.

This algorithm has O(n) runtime. Is there anything wrong with this algorithm?

In the article, They have declared an array of size n, and then laid the index of the k sized binary to hold into an array, for example if n = 7, k = 3 arr becomes [0, 1, 2, 0, 1, 2, 0]. And then connected the indices of the k sized binary which should be same by going through the property of palindrome which is kth and (n – k – 1)th variable should be same. And then they apply dfs on 0. For more clearance, please see the article above.

We already know which nodes would be connected to index 0 (that I have done in my algorithm), then why are we connecting all the indices ?

Is there something, I am missing?

I suspect that when n is not a mutiple of k then you may not get the desired wrapping effect.

In particular, let me interpret "after every k places from the start" as "the (k+1)th position in the array" - assuming 1-based indexing. Then in the given example on that page, with k = 4 and n = 10, your algorithm produces 1 0 0 0 1 1 0 0 0 1 - which is not a 4-length binary string being repeated and wrapped off at the end (the right answer would be 1 1 0 0 1 1 0 0 1 1.

If I am off-by-one on interpreting "k places from the start" (so say you were refering to the kth position), then even with n = 5 and k = 3 we get 1 0 1 0 1, whereas the right answer would be 1 1 0 1 1.

• Sorry, my mistake I meant to write after every k-1 places. In your particular examples, we will get the desired result. – shiwang Jun 20 '18 at 11:29
• So for k = 3, "after 2 places" would mean the 3rd position in the array, right? So don't you get 1 0 1 0 1? If you meant "on the 2nd place", then for k = 2, won't you always get the string 1 0 ... 0 1? Sorry if I am missing something here... – Neeldhara Jun 20 '18 at 11:41
• For n=5,k=3. When you put 1 at index 0 you have to repeatedly append a palindrome if size k now you have to put 1 at index k also and so on. Same from the end. So, traversing from start in case n=5,k=3 you will get 10010 and traversing from end you will get 01001. So, joining them both you will get 11011. – shiwang Jun 20 '18 at 11:59
• Then for n = 10, k = 4, don't you get 1000100000 and 1000110001, as stated above? – Neeldhara Jun 20 '18 at 12:47
• Yes, 1000110001 is the desired result in this case – shiwang Jun 20 '18 at 16:44