Monthly Archive for January, 2010

All the numbers which are palindromic in both base 10 and 2 were needed by the Problem 36 of Project Euler. One obvious thing which comes immediately is that since the number needs to be a palindrome in base as well, it as to be odd. So we check for only the odd numbers which reduces the effort by half.

I went ahead and made a method which reverses a given  number. If the number and its reverse are the same then the number is a palindrome. If the number is a palindrome in one base, check for the same property in the other base.

However, Project Euler has provided a better solution to this problem. In this particular question, palindromes up to 1 million were needed to be checked. So using my method, there would be a need to check 500000 numbers. A simpler thing to do would be to generate palindromes in one base and check for their property in the other base. Take for instance the number xyz, two possible palindromes are xyzyx and xyzzyx. Going by this method, the effort reduces to generating approximately 2000 palindromes in one base and checking for their validity in the other base!

Below are the classes I used to get the work done. I have mentioned both the solutions – anuvratSolution and projectEulerSolution. anuvratSolution uses the checkIfPalindrome method with respective bases from the PalindromeUtil class, while the projectEulerSolution uses makePalindrome from the same class to make a palindrome in base 2, and then checkIfPalindrome with base as 10 to get the solution.

The Radix enum class:

package pba.common.enums.number;

public enum Radix {
	DECIMAL("Decimal - Base 10", 10), BINARY("Binary - Base 2", 2);

	private final String m_name;
	private final int m_base;

	Radix(String name, int base) {
		m_name = name;
		m_base = base;
	}

	public String getName() {
		return m_name;
	}

	public int getBase() {
		return m_base;
	}
}

The NumberUtil class:

package pba.common.number;

import pba.common.enums.number.Radix;

public class NumberUtil {
	/**
	 * Given a number, reverse it.
	 *
	 * @param number The number, in base 10, which needs to be reversed without any leading zeroes.
	 * @return The reversed number, in base 10, without any leading zeroes
	 */
	public static long reverse(long number, Radix base) {
		long reversed = 0;
		while (number > 0) {
			reversed = base.getBase() * reversed + number % base.getBase();
			number /= base.getBase();
		}
		return reversed;
	}
}

The PalindromeUtil class:

package pba.common.tools;

import pba.common.enums.number.Radix;
import pba.common.number.NumberUtil;

public class PalindromeUtil {
	/**
	 * @param number The number which needs to be checked in base 10
	 * @param base The base in which the number is to be checked for palindrome property
	 * @return True if the number is a palindrome, false otherwise
	 */
	public static boolean checkIfPalindrome(long number, Radix base) {
		return number == NumberUtil.reverse(number, base);
	}

	/**
	 * Given a number, it forms a palindrome out of it. For example, for the number xyz, the possible palindromes are
	 * xyzzyx and xyzyx.
	 *
	 * @param number The number out of which a palindrome needs to be made
	 * @param base The base in which the construction is done, for example, decimal, binary, octal, etc.
	 * @param oddLength Specifies whether the constructed number is to be of odd length or even length. For the example
	 *            mentioned above, if oddLength was true, the the number returned would be xyzyx.
	 * @return A palindrome formed using the number provided and having length parity as specified
	 */
	public static long makePalindrome(long number, Radix base, boolean oddLength) {
		long palin = number;
		if (oddLength)
			number /= base.getBase();

		while (number > 0) {
			palin = base.getBase() * palin + number % base.getBase();
			number /= base.getBase();
		}

		return palin;
	}
}

The Problem_36 class:

package problems_31_40;

import pba.common.enums.number.Radix;
import pba.common.tools.PalindromeUtil;

public class Problem_36 {
	private static final int MAX_NUMBER = 1000000;

	public static void anuvratSolution(String[] args) {
		long sum = 0;
		for (int i = 1; i < Problem_36.MAX_NUMBER; i += 2)
			if (PalindromeUtil.checkIfPalindrome(i, Radix.DECIMAL) &amp;amp;&amp;amp; PalindromeUtil.checkIfPalindrome(i, Radix.BINARY))
				sum += i;
		System.out.println(sum);
	}

	public static void projectEulerSolution(String[] args) {
		long sum = 0;
		for (int iter = 0; iter < 2; iter++) {
			boolean oddLength = iter == 0 ? true : false;
			for (int i = 1;; i++) {
				long palin = PalindromeUtil.makePalindrome(i, Radix.BINARY, oddLength);
				if (palin > Problem_36.MAX_NUMBER)
					break;
				if (PalindromeUtil.checkIfPalindrome(palin, Radix.DECIMAL))
					sum += palin;
			}
		}
		System.out.println(sum);
	}

	public static void main(String[] args) {
		Problem_36.projectEulerSolution(args);
		// Problem_36.anuvratSolution(args);
	}
}

Popularity: 13% [?]