Double base palindrome

Question:
The decimal number 585 = 1001001001 (binary) is palindromic in both bases.
Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2.


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!