Generate Max Number from an Integer Array

To contact us Click HERE
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;	}}