Reputation: 85
Sample input:
4
123 124 56 90
I'm to find the largest possible number you can get by combining each of these numbers together in whatever possible way.
So, the possible combinations for those numbers are {1231245690, 1241235690, 5612312490, 9012312456, 9056124123, etc.}, with the largest number being 9056124123.
I'm thinking of this problem like this: The largest number would start with the largest last digit in the set. So, the largest number here would start with "9", therefore 90 is the first number I'm concerned with. Then, I'm looking at the rest of the set with the largest last digit, which would be "5", so 56 is the second number I'm concerned with. If the largest last digit is a tie, I'd evaluate the second to last digit, etc.
For one, let me know if I'm the right track here with how I'm thinking about the problem, and if I am, which structures/types should I be looking at in order to implement this? Would this require something to do with bit manipulation? Because I'm a little stuck on that part.
Upvotes: 0
Views: 582
Reputation: 767
Carefully examine where the numbers are placed in your sample output. 90 56 124 123 The numbers go from greatest to least, depending on what the biggest digit is from the left. (Biggest first digit - @Mark)
There are possible inputs which require tiebreaking. Given the numbers '80, 807, and 000'
Compare them from left to right.
8 0
| |\
8 0 7
Because 807 is longer than 80, compare the last bit of 807 (7) to 80.
7
|
8 0
Comparison completed, because the 8 of 80 was compared to the 7 of 807, showing that 80 should be first. Put 80 and 807 together and get 80807, and of course add the 000.
Upvotes: 3
Reputation: 4225
You are almost on right path. There is no need for bit manipulation. Sorting them using custom String comparator function as below is enough.
Collections.sort(inputArray, new Comparator < String > () {
public int compare(String a, String b) {
//if a = "80", b = "807"
String ab = a + b; // 80807
String ba = b + a; //80780
// now compare
return ab.compareTo(ba) > 0 ? -1 : 1;
}
});
later concat them.
@Dawood ibn Kareem Thanks for pointing out the edge case.
Upvotes: 3
Reputation: 313
Convert the numbers to strings, pad them with "X" on the right to make them all the same length, sort descending, concatenate removing the "X"s, there is your result.
Upvotes: 1
Reputation: 140525
You are on a good path!
The easiest to go about types is to turn the numbers into strings. That allows you to quickly access the first, second,... digit of the original numbers. And concatenation is also much easier to do for strings!
Upvotes: 1