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:
See how to check if a String is a palindrome in O(n/2) time here.
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!