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-
- I will declare a string of size n with all the entries 0.
- Leftmost character has to be 1, so to be a palindrome rightmost should also be a 1 .
- Now after every k-1 places starting from start, I will put a 1.
- 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?