Generate Max Number from an Integer Array

Question:

You are given a list of positive int numbers, find out the max number that can be comprised of these input int numbers.

Example:

For input 1, 2, 3, the max number would be 321.

For 8, 87, 896, the max number would be 896887.

Answer:

For example, if the numbers are 24, 243, 2435? The max number should be [2435][243][24].

Is there a way we can sort this array, and get a new array: [2435, 243, 24]?

When we sort this array, we can define a comparator. When it compares two numbers (say a and b), if the two numbers has same digit numbers, we directly compare it, if they have different digit numbers (say a has less digit numbers than b), for the number (a in this case) has less digit numbers, we would get a new int number (get a new int a0 from b) by right padding it with the original digit numbers, and get a new number a0, then compare a0 and b.

So when compare 24 and 2435, we would think we are actually comparing 2[424] and 2435, so in the descending sorted array, 2535 would come before 24.

So the descending sorted array would be [2435, 243, 24], as 2435 > 243[2] > 24[24]; the generated max number would be [2435][243][24], this would be exactly what we expect.

Code:

The complete algorithm/test code and also many other algorithm problems and solutions are available from https://github.com/programmer-plus.

package org.codeexample.maxNumber;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
import org.codeexample.common.OverflowException;
import org.codeexample.common.Utils;
class MyComparator implements Comparator<Integer> {
	/**
	 * For input 87 and 8, it would return -1, for 89 and 8, return 1, for 88
	 * and 8, return 0.
	 */
	public int compare(Integer int1, Integer int2) {
		if (int1 == null)
			return -1;
		if (int2 == null)
			return 1;
		// if eqauls, return directly to improve efficiency.
		if (int1.equals(int2))
			return 0;
		int int1DigitNumber = Utils.getNumberOfDigits(int1), int2DigitNumber = Utils
				.getNumberOfDigits(int2);
		if (int1DigitNumber > int2DigitNumber) {
			int2 = rightPadNumber(int2, int1DigitNumber);
		} else if (int1DigitNumber < int2DigitNumber) {
			int1 = rightPadNumber(int1, int2DigitNumber);
		}
		return int1.compareTo(int2);
	}
	/**
	 * @param ia
	 * @param newDigitalNumber
	 * @return pad the number by the original digital numbers in order. <br>
	 *         For example, for input 98, 5, it would return 98989 - five
	 *         numbers.
	 * @throws IllegalArgumentException,
	 *             if the new digital number is less than the digital number of
	 *             the old integer.
	 * @throws OverflowException,
	 *             if the generated number would be larger than
	 *             Integer.MAX_VALUE
	 */
	public static int rightPadNumber(int ia,
			int newDigitalNumber)
			throws IllegalArgumentException,
			OverflowException {
		int oldNumbers = Utils.getNumberOfDigits(ia);
		if (oldNumbers > newDigitalNumber) {
			throw new IllegalArgumentException(
					"Invalid parameters: "
							+ ia
							+ " has "
							+ oldNumbers
							+ " digits, its larger than the specified new digit number: "
							+ newDigitalNumber);
		} else if (oldNumbers == newDigitalNumber) {
			return ia; // Improve efficiency.
		}
		// example: to pad 98 to five numbers: 98988.
		boolean negative = ia < 0;
		if (negative) {
			ia = -ia;
		}
		String orginalString = String.valueOf(ia);
		StringBuffer resultString = new StringBuffer(
				orginalString);
		int diff = newDigitalNumber - oldNumbers;
		while (diff >= oldNumbers) {
			resultString.append(orginalString);
			diff -= oldNumbers;
		}
		// now, result = 9898, diff = 1;
		if (diff > 0) {
			resultString.append(orginalString.substring(0,
					diff));
		}
		if (negative) {
			resultString.insert(0, "-");
		}
		try {
			return Integer.valueOf(resultString.toString());
		} catch (NumberFormatException e) {
			throw new OverflowException(e);
		}
	}
}
public class MaxNumber {
	/**
	 * @see org.codeexample.maxNumber#maxNumber(java.util.List)
	 */
	public static int maxNumber(int[] ia)
			throws IllegalArgumentException,
			OverflowException {
		return maxNumber(Utils.toList(ia));
	}
	/**
	 * @param la,
	 *            a list of positive Integer numbers
	 * @return the max value that is generated by concatting each Integer value<br>
	 *         For example, for input 8, 87, 89, it would return 89887
	 * @throws IllegalArgumentException,
	 *             if the parameters include negative number
	 * @throws OverflowException,
	 *             if the generated number would be larger than
	 *             Integer.MAX_VALUE
	 */
	public static int maxNumber(List<Integer> la)
			throws IllegalArgumentException,
			OverflowException {
		Collections.sort(la, new MyComparator());
		Collections.reverse(la);
		Iterator<Integer> iterator = la.iterator();
		int result = 0;
		while (iterator.hasNext()) {
			int tmpi = iterator.next();
			if (tmpi < 0) {
				throw new IllegalArgumentException(
						"The list contains negative number: "
								+ tmpi);
			}
			int digitNumber = Utils.getNumberOfDigits(tmpi);
			// result = (10^digitNumber)*result + tmpi;
			result = Utils.safeMultiply(new Double(Math
					.pow(10, digitNumber)).intValue(),
					result);
			result = Utils.safeAdd(result, tmpi);
		}
		return result;
	}
}