Click here to Skip to main content
15,119,116 members
Articles / General Programming / Algorithms
Article
Posted 27 Jan 2017

Stats

17.1K views
9 bookmarked

Finding nth Binary Palindrome in C#

Rate me:
Please Sign up or sign in to vote.
4.67/5 (13 votes)
27 Jan 2017CPOL3 min read
This short article provides a method of calculating nth binary palindrome using some math in C# code.

Introduction

This article provides a method of calculating nth binary palindrome using some math in C# code. I find it useful since all the methods I found using Google had a different approach and were relying on precalculating to array or were using brute force iteration.

Background

The basic idea for this algorithm is to construct the nth palindrome rather than detect it without a need to construct any other palindrome than the required one.

What I did is I divided each binary palindrome into the left side and right side since one should be the reverse of the other. The following snippet illustrates this division.

---------------Initial Group------------
   0
   1

---------------Group 0------------------
  1|1

  101
  111

---------------Group 1------------------
 10|01
 11|11

 10001
 10101
 11011
 11111

---------------Group 2------------------
100|001
101|101
110|011
111|111

1000001
1001001
1010101
1011101
1100011
1101011
1110111
1111111

and so on ...

In a snippet above, first, consecutive binary palindromes are divided into groups by the number of digits. In group 0, there are palindromes with 2 and 3 digits, in group 1 palindromes with 4 and 5 digits and so on. For better visualization, I put "|" sign in the middle of palindromes with even digits number.

Now, if we forget about the initial group and group 0 which could be just constants, we can start to think about the algorithm. The first thing that we need to do is to compute in which group our nth element will be. Here, binary logarithm comes in handy:

C#
groupIndex = floor(log2((nth / 3) + 1))

Division by 3 is required here since our group can be divided into 3 sub-groups:

  • without digits between sides ('|' sign is used for ilustration),
  • with '0' between sides
  • with '1' between sides

Now we can compute number of elements in each sub-group:

C#
subGroupCount = 2 ^ groupIndex

And number of binary palindromes which are before current group (using an adapted sum of geometric sequence formula):

C#
Sum = ((2 ^ groupIndex) - 1) * 3

Let's calculate the index of desired palindrome inside its group:

C#
var insideGroupIndex = nth - Sum;

and the index inside sub-group:

C#
var insideSubGroupIndex = insideGroupIndex % subGroupCount;

Now we can figure out if our binary palindrome has no digit, '0' or '1' between sides (it is an index of a sub group):

C#
var opType = (int)Math.Floor((double)insideGroupIndex / subGroupCount);

Now we have everything to assemble our palindrome but we have to do it differently for each of 3 sub groups inside a group:

  • if (opType == 0) left side of a binary palindrome should be "1" + binaryStringRepresentation(subGroupIndex) padded left to digits count in a group. There should be no connector between sides
  • if (opType == 1) left side of a binary palindrome should be "1" + binaryStringRepresentation(subGroupIndex / 2) padded left to digits count in a group. Connector should be '0' or '1' based on if groupIndex is divisible by 2 (even or odd)
  • if (opType == 2) left side of a binary palindrome should be "1" + binaryStringRepresentation((subGroupIndex / 2) + (subGroupCount / 2)) padded left to digits count in a group. Connector should be '0' or '1' based on if groupIndex is divisible by 2 (even or odd)

Finally, the output should be:

C#
output = leftSide + connector + reverse(leftSide)

Using the Code

The code for this algorithm looks like this:

C#
private string GetNthBinaryPalindrome(int n)
{
    switch (n)
    {
        case 1:
            return "0";
        case 2:
            return "1";
        case 3:
            return "11";
        case 4:
            return "101";
        case 5:
            return "111";
        default:
            if (n < 1) 
                return null;
                
            var S = n - 3;
            var groupIndex = (int)Math.Floor(Math.Log((S / 3) + 1, 2));
            var digitsCount = group;
            var subGroupCount = (int)Math.Round(Math.Pow(2, group));
            var Sn = (subGroupCount - 1) * 3;
            var insideGroupIndex = S - Sn;
            var subGroupIndex = insideGroupIndex % subGroupCount;
            var opType = (int)Math.Floor((double)insideGroupIndex / subGroupCount);
            
            string leftSide;
            string connector;
            
            switch (opType)
            {
                case 0:
                    connector = "";
                    leftSide = "1" + 
                    Convert.ToString(subGroupIndex, 2).PadLeft(digitsCount, '0');
                    break;
                case 1:
                    connector = ((groupIndex & 1) == 0) ? "0" : "1";
                    leftSide = "1" + 
                    Convert.ToString(subGroupIndex / 2, 2).PadLeft(digitsCount, '0');
                    break;
                case 2:
                    connector = ((groupIndex & 1) == 0) ? "0" : "1";
                    leftSide = "1" + Convert.ToString(subGroupIndex / 2 + 
                    subGroupCount / 2, 2).PadLeft(digitsCount, '0');
                    break;
                default:
                    return null;
            }
            
            return String.Format("{0}{1}{2}", 
            leftSide, connector, String.Join("", leftSide.Reverse()));
    }
}

Points of Interest

This algorithm could be probably even more optimized but for my purposes, it was efficient enough.

History

  • 21st December, 2016: Initial version
  • 23st December, 2016: Corrected typo in palindromes list Group 1

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

wlf84k
Unknown
No Biography provided

Comments and Discussions

 
Questionwhat is value of group Pin
Kartik Singla18-Jul-17 8:11
MemberKartik Singla18-Jul-17 8:11 
QuestionMinor typo? Pin
Member 986208222-Dec-16 23:36
MemberMember 986208222-Dec-16 23:36 
AnswerRe: Minor typo? Pin
wlf84k23-Dec-16 9:30
Memberwlf84k23-Dec-16 9:30 
You are right about both. There was a typo (corrected now) and this is a purely curiosity-driven excercise indeed. The problem itself is taken from an algorithm contest, so it is rather for fun. On the other hand, who knows, maybe it would be useful somewhere, somehow, for someone ... Wink | ;)

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.