# 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.

Related Tags:

## 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)) {
}
}

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();

}

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!

Next Challenge: