Here is a Java impl...
public class LargestPossibleNumber {
static class LPNComparator implements Comparator<String> {
@Override
public int compare(String s1, String s2) {
int l1 = s1.length(); // new element
int l2 = s2.length(); // existing element
if (l1 == l2) {
for (int i1 = 0, i2 = 0; i1 < l1 && i2 < l2; i1++, i2++) {
char c1 = s1.charAt(i1);
char c2 = s2.charAt(i2);
if (c1 != c2) {
return c1 - c2;
}
}
return 0;
} else if (l1 < l2) { // padding
StringBuilder s = new StringBuilder(s1);
for (int i = 0; i < l2 - l1; i++) {
s.append(s1.charAt(l1 - 1));
}
s1 = s.toString();
for (int i1 = 0, i2 = 0; i2 < l2; i1++, i2++) {
char c1 = s1.charAt(i1);
char c2 = s2.charAt(i2);
if (c1 != c2) {
return c1 - c2;
}
}
return 1;
} else { // l1 > l2 // padding
StringBuilder s = new StringBuilder(s2);
for (int i = 0; i < l1 - l2; i++) {
s.append(s2.charAt(l2 - 1));
}
s2 = s.toString();
for (int i1 = 0, i2 = 0; i2 < l1; i1++, i2++) {
char c1 = s1.charAt(i1);
char c2 = s2.charAt(i2);
if (c1 != c2) {
return c1 - c2;
}
}
return -1;
}
}
}
public static String getLNP(TreeSet<String> set) {
Iterator<String> iter = set.iterator();
StringBuilder sBuilder = new StringBuilder();
while (iter.hasNext()) {
String element = iter.next();
sBuilder.insert(0, element);
}
return sBuilder.toString();
}
public static void main(String args[]) {
TreeSet<String> set = new TreeSet<String>(new LPNComparator());
set.add("9"); set.add("10");
System.out.println(getLNP(set)); //910
set.clear();set.add("2");set.add("3");set.add("5");set.add("78");
System.out.println(getLNP(set)); //78532
set.clear();set.add("10");set.add("100");
System.out.println(getLNP(set)); //10100 *
set.clear();set.add("9");set.add("100");
System.out.println(getLNP(set)); //9100
set.clear();set.add("2");set.add("3");set.add("9");set.add("78");
System.out.println(getLNP(set)); //97832
set.clear();set.add("101");set.add("10");
System.out.println(getLNP(set)); //10110
set.clear();set.add("97");set.add("8");set.add("9");
System.out.println(getLNP(set)); //9978 *
set.clear();set.add("8");set.add("87");set.add("89");
System.out.println(getLNP(set)); // 89887 *
}
}
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
