Double base palindrome

Binary Palindromes

All binary palindromes must be odd. This is because we will never have a case where zero at its 0th place. If statement wasn't true, we would need a zero at the opposite end, which can't be since all zero's preceding the first non-zero digit are removed.

For example, we don't write 010010, but instead we write just 10010.

Algorithm Pseudocode

The algorithm pseudocode for converting a number to binary is as follows:

Converting a number to binary

1. Find out how many placeholders are necessary to fit the entire number. We do this by finding the first power of 2 number that is greater than our value.
2. Each time we divide our input by two, if our result is odd, append a 1, otherwise a 0.
3. Once done, return the completed String.

Checking if a String is a palindrome

See how to check if a String is a palindrome in O(n/2) time here.

Calculating all palindromes below a million

1. Checking only odd values, find the values that are palindrome and append them to a list.
2. Iterating through this list, sum each one where their binaries are also palindromes.
3. Return the sum.

Implementation in Java

import java.util.ArrayList; 

public class DoubleBasePalindrome {
	public static void main(String[] args) {

		System.out.println(findDoubleBaseSum(1000000));	

	}	

	static int findDoubleBaseSum(int max) {

		ArrayList<Integer> list = new ArrayList<>();

		// Only odds can be palindromes
		for (int i = 1; i < max; i += 2) {
			if (isPalindrome(i)) {
				list.add(i);
			}
		}

		String binary = "";
		int sum = 0;

		for (Integer i : list) {
			binary = convertToBinary(i);
			if (isPalindrome(binary))
				sum += i;
		}

		return sum;

	}

	static String convertToBinary(int input) {

		// get a number

		StringBuilder bin = new StringBuilder();

		int maxPower = 0;

		// get the largest power of two that can get
		for (int i = 0; i < Integer.MAX_VALUE; i++) {
			if (Math.pow(2, i) > input) {
				maxPower = i;
				break;
			}
		}

		// For each iteration, divide by two and append a binary place
		for (int i = 0; i < maxPower; i++) {
			if (input % 2 != 0) {
				bin.append(0);
			} else {
				bin.append(1);
			}
			input /= 2;
		}

		return bin.toString();

	}

	// Operator overloading
	static boolean isPalindrome(int input) {
		return isPalindrome(String.valueOf(input));
	}

	public static boolean isPalindrome(String input) {

		// Break into a char array
		char[] charArray = input.toCharArray();

		// Compare front and end character until meet at middle
		for (int i = 0, j = charArray.length-1; i < charArray.length / 2; i++, j--) {
			if (charArray[i] != charArray[j])
				return false;
		}

		return true;

	}
}

Sources

This question was taken from Project Euler, Problem 36.

Came up with a better solution or have a question? Comment below!