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

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

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

- 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.
- Each time we divide our input by two, if our result is odd, append a
`1`, otherwise a`0`. - Once done, return the completed String.

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

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

```
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;
}
}
```

This question was taken from Project Euler, Problem 36.

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

Next Challenge: Number of canoes needed