nth Binary palindrome with efficient time complexity

Question

Given an integer N, i am trying to find the nth binary palindrome.I have written the following code but it is not efficient.is there a more efficient way in terms of time complexity. I was trying it out as a problem online and i was supposed to output in 1 sec or less but for every input it takes 2 seconds.

public static Boolean Palind(String n){
    String reverse = "";
    int length = n.length();
    for(int i = length - 1; i >=0;i--){
        reverse = reverse + n.charAt(i);
    }
    if(n.equals(reverse)){
        return true;
    }
    else{
        return false;
    }
}

public static int Magical(int n){
    ArrayList<Integer> res = new ArrayList<Integer>();
    for(int i = 1; i < Math.pow(2, n);i++){
        if(Palind(Integer.toBinaryString(i))){
            res.add(i);
        }
    }
    return res.get(n-1);
}

Probably not - the question is specifically about performance and is perfectly on topic here. — assylias, Dec 24 '16 at 09:51
http://stackoverflow.com/questions/3165776/reverse-bits-in-number — assylias, Dec 24 '16 at 09:54
Why do you need to store all palindromes in the array? Make some `int count = 0`. Increment it every time you find palindrome, return current palindrome `if count == n`. Then just a little optimization, you don't need to check if the whole number equals reversed number. You just need to check if first half of the number equals reversed second part. — Yevhen Kuzmovych, Dec 24 '16 at 09:57

TheConstructor · Answer 1 · 2017-01-18T21:46:56.803

Try something like this maybe?

public static void main(String[] args) {
    for (int i = 1; i < 65535; i++) {
        System.out.println(
                i + ": " + getBinaryPalindrom(i) + " = " + Integer.toBinaryString(getBinaryPalindrom(i)));
    }
}

public static int getBinaryPalindrom(int N) {
    if (N < 4) {
        switch (N) {
            case 1:
                return 0;
            case 2:
                return 1;
            case 3:
                return 3;
        }
        throw new IndexOutOfBoundsException("You need to supply N >= 1");
    }
    // second highest to keep the right length (highest is always 1)
    final int bitAfterHighest = (N >>> (Integer.SIZE - Integer.numberOfLeadingZeros(N) - 2)) & 1;
    // now remove the second highest bit to get the left half of our palindrom
    final int leftHalf = (((N >>> (Integer.SIZE - Integer.numberOfLeadingZeros(N) - 1)) & 1) << (Integer.SIZE -
            Integer.numberOfLeadingZeros(N) - 2)) | ((N << (Integer.numberOfLeadingZeros(N) + 2)) >>> (Integer.numberOfLeadingZeros(N) + 2));
    // right half is just the left reversed
    final int rightHalf = Integer.reverse(leftHalf);
    if (Integer.numberOfLeadingZeros(leftHalf) < Integer.SIZE / 2) {
        throw new IndexOutOfBoundsException("To big to fit N=" + N + " into an int");
    }
    if (bitAfterHighest == 0) {
        // First uneven-length palindromes
        return (leftHalf << (Integer.SIZE - Integer.numberOfLeadingZeros(leftHalf)) - 1) | (rightHalf
                >>> Integer.numberOfTrailingZeros(rightHalf));
    } else {
        // Then even-length palindromes
        return (leftHalf << (Integer.SIZE - Integer.numberOfLeadingZeros(leftHalf))) | (rightHalf
                >>> Integer.numberOfTrailingZeros(rightHalf));
    }
}

The idea is that each number will become a palindrome once it reverse is added. To have the halves correctly aligned the halves just need to be shifted in place.

The problem why this has gotten a bit complex is that all uneven-length palindromes of a given leftHalf length come before all even-length palindromes of a given leftHalf length. Feel free to provide a better solution.

As int has 32 bit in Java there is a limit on N.

int-Version on ideone.com

And a BigInteger-version to support big values. It is not as fast as the int-version as the byte[]-arrays which store the value of the BigInteger create some overhead.

public static void main(String[] args) {
    for (BigInteger i = BigInteger.valueOf(12345678); i.compareTo(BigInteger.valueOf(12345778)) < 0; i = i
            .add(BigInteger
            .ONE)) {
        final BigInteger curr = getBinaryPalindrom(i);
        System.out.println(i + ": " + curr + " = " + curr.toString(2));
    }
}

public static BigInteger getBinaryPalindrom(BigInteger n) {
    if (n.compareTo(BigInteger.ZERO) <= 0) {
        throw new IndexOutOfBoundsException("You need to supply N >= 1");
    } else if (n.equals(BigInteger.valueOf(1))) {
        return BigInteger.valueOf(0);
    } else if (n.equals(BigInteger.valueOf(2))) {
        return BigInteger.valueOf(1);
    } else if (n.equals(BigInteger.valueOf(3))) {
        return BigInteger.valueOf(3);
    }
    final int bitLength = n.bitLength() - 1;

    // second highest to keep the right length (highest is always 1)
    final boolean bitAfterHighest = n.testBit(bitLength - 1);
    // now remove the second highest bit to get the left half of our palindrom
    final BigInteger leftHalf = n.clearBit(bitLength).setBit(bitLength - 1);
    // right half is just the left reversed
    final BigInteger rightHalf;
    {
        byte[] inArray = leftHalf.toByteArray();
        byte[] outArray = new byte[inArray.length];
        final int shiftOffset = Integer.SIZE - Byte.SIZE;
        for (int i = 0; i < inArray.length; i++) {
            outArray[inArray.length - 1 - i] = (byte) (Integer.reverse(inArray[i]) >>> shiftOffset);
        }
        rightHalf = new BigInteger(1, outArray).shiftRight(outArray.length * Byte.SIZE - bitLength);
    }
    if (!bitAfterHighest) {
        // First uneven-length palindromes
        return leftHalf.shiftLeft(bitLength - 1).or(rightHalf);
    } else {
        // Then even-length palindromes
        return leftHalf.shiftLeft(bitLength).or(rightHalf);
    }
}

@R.S. if n is 1*1*00101 I take the second highest bit to later decide whether the next palindrome has even or uneven length. Then I remove that bit leaving e.g. 100101 and build the final palindrome. Taking the second highest bit ensures that all lower bits can be used to count up, then we automatically switch to building even length and can again use all lower bits for counting. — TheConstructor, Feb 13 '18 at 06:07
each number will become a palindrome once it reverse is added.. How it state that it will gives nth palindrome? — R. S., Feb 13 '18 at 09:13
Longer palindrome have a higher numeric value. The left "upper" half of the palindrome is most significant for the order within the same length. Hence when I ensure that the upper half is generated in correct order (i.e. count), I ensure that the palindromes are in the correct order. — TheConstructor, Feb 13 '18 at 16:48

Chai T. Rex · Answer 2 · 2016-12-25T02:13:47.217

The relevant OEIS entry (A006995) has a lot of nice tips if you read through it. For example, a(2^n-1)=2^(2n-2)-1 lets you skip right to the (2ⁿ - 1)^th palindrome really quickly.

It also gives several implementations. For example, the Smalltalk implementation works like this (note that the input value, n, starts with 1 for the first palindrome, 0):

public static final int nthBooleanPalindrome(int n) {
    if (n == 1) return 0;
    if (n == 2) return 1;
    int m = 31 - Integer.numberOfLeadingZeros(n);
    int c = 1 << (m - 1);
    int b;
    if (n >= 3*c) {
        int a = n - 3*c;
        int d = 2*c*c;
        b = d + 1;
        int k2 = 1;
        for (int i = 1; i < m; i++) {
            k2 <<= 1;
            b += a*k2/c%2*(k2 + d/k2);
        }
    }
    else {
        int a = n - 2*c;
        int d = c*c;
        b = d + 1 + (n%2*c);
        int k2 = 1;
        for (int i = 1; i < m - 1; i++) {
            k2 <<= 1;
            b += a*k2/c%2*(k2 + d/k2);
        }
    }
    return b;
}

Right, the original was Smalltalk (see the Smalltalk code in the OEIS link) and I translated it to Java to answer the question about how to do it in Java. — Chai T. Rex, Dec 27 '16 at 19:00

score 0 · Answer 3 · edited Jul 10 '19 at 11:22

Idea to optimize, Let's look at the palindrome sequence 0, 1, 11, 101, 111, 1001 etc...

All numbers must begin and end with 1, So the middle bits only changes and midle substring should be palindrome for full string to become palindrome,

So let's take a 2 digit binary number - one palindrome is possible.

The binary of the decimal 3 is a palindrome. 11
For a 3 digit binary number 2 palindromes are possible, 2*(no of 1 digit palindrome)

The binary of the decimal 5 is a palindrome. 101

The binary of the decimal 7 is a palindrome. 111
For 5 digit binary number 4 palindromes are possible 2*(no of 3 digit palindrome)

10001,10101, 11011, 11111

and so on,

So it will be 2 + 2⁰ + 2¹ + 2² +...... +2^i-N ,

we solve for i and find out the palindrome number.

So by analysing this sequence we get an equation like 2^(i/2)+1 -1 = N

where N is the No of palindrome,

and i is the number of bits in the nth palindrome string,

using this we can find the length of the String, from this we can find the string early.

This might be complex, but helps in solving higher values of N quickly....

Is 0 and 1 are considered as palindrome? – Kiran Kumar Dec 24 '16 at 10:17 — Kiran Kumar, Dec 24 '16 at 10:17
why not? It's trivial but still valid. – TheConstructor Dec 24 '16 at 20:08 — TheConstructor, Dec 24 '16 at 20:08

Tony · Answer 4 · 2017-06-06T14:35:57.970

I have the same idea with @Kiran Kumar: you should not count number one by one to find if it is a binary palindrome which is too slow, but rather find the internal pattern that number has.

List the number in binary string one by one, you can find the pattern:

0
1
11
101
1001
1111
...
1......1

And the following is some math problem: We have 2^round_up((L-2)/2) palindrome of number with length L in binary format. Sum up every shorter length number, we get following len to sum mapping:

for (int i = 1; i < mapping.length; i++) {
    mapping[i] = (long) (mapping[i - 1] + Math.pow(2, Math.ceil((i - 1) * 1.0 / 2)));
}

If we find N range in [count(L), count(L+1)), we can concat it with remaining number:

public static long magical(long n) {
    if (n == 0 || n == 1) {
        return n;
    }
    long N = n - 2;
    return Long.parseLong(concat(N), 2);
}

private static String concat(long N) {
    int midLen = Arrays.binarySearch(indexRange, N);
    if (midLen < 0) {
        midLen = -midLen - 1;
    }
    long remaining = N - indexRange[midLen];
    String mid = mirror(remaining, midLen);
    return '1' + mid + '1';
}

private static String mirror(long n, int midLen) {
    int halfLen = (int) Math.ceil(midLen * 1.0 / 2);
    // produce fixed length binary string
    final String half = Long.toBinaryString(n | (1 << halfLen)).substring(1);
    if (midLen % 2 == 0) {
        return half + new StringBuilder(half).reverse().toString();
    } else {
        return half + new StringBuilder(half).reverse().toString().substring(1);
    }
}

Full code with test for produce large possible long can be found in my git repo.

i can not able to find full code on your mention git repo. can you please update your code as I need it badly. — jenitshah, Jun 06 '17 at 11:23

nth Binary palindrome with efficient time complexity

4 Answers4