1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Sorry, my mistake I meant to write after every k-1 places. In your particular examples, we will get the desired result. $\endgroup$ – shiwang Jun 20 '18 at 11:29
  • 1
    $\begingroup$ 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... $\endgroup$ – Neeldhara Jun 20 '18 at 11:41
  • 1
    $\begingroup$ 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. $\endgroup$ – shiwang Jun 20 '18 at 11:59
  • 1
    $\begingroup$ Then for n = 10, k = 4, don't you get 1000100000 and 1000110001, as stated above? $\endgroup$ – Neeldhara Jun 20 '18 at 12:47
  • 1
    $\begingroup$ Yes, 1000110001 is the desired result in this case $\endgroup$ – shiwang Jun 20 '18 at 16:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.