Author |
Topic: Sort array to get max concatinated value (Read 3930 times) |
|
birbal
Full Member
Gender: 
Posts: 250
|
 |
Sort array to get max concatinated value
« on: Apr 11th, 2011, 7:48am » |
 Quote  Modify
|
Given an integer array, sort the integer array such that the concatenated integer of the result array is max. e.g. [4, 94, 9, 14, 1] will be sorted to [9,94,4,14,1] where the result integer is 9944141
|
|
 IP Logged |
The only thing we have to fear is fear itself!
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: Sort array to get max concatinated value
« Reply #1 on: Apr 11th, 2011, 10:32am » |
Quote Modify
|
on Apr 11th, 2011, 7:48am, birbal wrote:| Given an integer array, sort the integer array such that the concatenated integer of the result array is max. e.g. [4, 94, 9, 14, 1] will be sorted to [9,94,4,14,1] where the result integer is 9944141 |
|
Looks like a greedy approach should work, using a lexicographic descending sort (with "end of number" coming before all digits).
Edit: hm, no, that would put 1 before 14. We could treat "end of number" as "last digit + 0.5", though.
|
| « Last Edit: Apr 11th, 2011, 10:35am by pex » |
IP Logged |
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Sort array to get max concatinated value
« Reply #2 on: Apr 11th, 2011, 9:58pm » |
Quote Modify
|
I think for any two numbers A and B,
if (value(A.B) > value(B.A)), then A would come before B in the sorted and vice versa. But i cudnt really prove this 
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: Sort array to get max concatinated value
« Reply #3 on: Apr 11th, 2011, 10:55pm » |
Quote Modify
|
on Apr 11th, 2011, 9:58pm, birbal wrote:I think for any two numbers A and B,
if (value(A.B) > value(B.A)), then A would come before B in the sorted and vice versa. But i cudnt really prove this |
|
Yeah, that's the more understandable version of what I was trying to say.  Think of how you would compare two very large integers, which you know have the same number of digits, by hand: you would first compare the most significant digits, break a tie using the second-most significant digits, etc. So in this problem, when you are constructing the number from left to right, the optimal thing to do at each step is to add the number that has the largest most significant digit, with the same tie-breaking rules.
|
|
IP Logged |
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Sort array to get max concatinated value
« Reply #4 on: Apr 12th, 2011, 1:05am » |
Quote Modify
|
on Apr 11th, 2011, 10:55pm, pex wrote:
Yeah, that's the more understandable version of what I was trying to say. Think of how you would compare two very large integers, which you know have the same number of digits, by hand: you would first compare the most significant digits, break a tie using the second-most significant digits, etc. So in this problem, when you are constructing the number from left to right, the optimal thing to do at each step is to add the number that has the largest most significant digit, with the same tie-breaking rules. |
|
No i was trying to say something different. If the numbers have same number of digits, then it would be a simple integer comparison. But if number of digits are different in both the numbers, then we have to check the concatenated value.
For example
A = 1
B = 12
A.B = 112
B.A = 121
B.A > A.B, hence B comes before A in the sorted.
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: Sort array to get max concatinated value
« Reply #5 on: Apr 12th, 2011, 1:19am » |
Quote Modify
|
Yes. My remark about numbers of the same length was about comparing the results of different concatenation orders, sorry about the confusion.
If we apply the lexicographic sort I described above to your example, treating "end of number" as "last digit + 0.5", we would represent A = 1 as [1, 1.5] and B = 12 as [1, 2, 2.5]. First compare the first digits: 1=1, so we need to look at the next digits. 1.5<2, so B should come before A.
|
|
IP Logged |
|
|
|
baskin
Newbie
Gender:
Posts: 26
|
|
Re: Sort array to get max concatinated value
« Reply #6 on: May 26th, 2011, 5:01am » |
Quote Modify
|
How about this?
Compare each pair of integers using the concatenated string value instead of normal integer comparison.
Code:
public static void main(String[] args)
{
int []a = new int[]{4, 94, 9, 14, 1};
Util.print(a);
SortUtil.quickSort(a, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return (o2.toString() + o1).compareTo(o1.toString() + o2);
}
});
Util.print(a);
}
|
|
o/p
4 94 9 14 1
9 94 4 14 1
|
|
IP Logged |
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Sort array to get max concatinated value
« Reply #7 on: Jun 2nd, 2011, 5:18am » |
Quote Modify
|
on May 26th, 2011, 5:01am, baskin wrote:How about this?
Compare each pair of integers using the concatenated string value instead of normal integer comparison.
Code:
public static void main(String[] args)
{
int []a = new int[]{4, 94, 9, 14, 1};
Util.print(a);
SortUtil.quickSort(a, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return (o2.toString() + o1).compareTo(o1.toString() + o2);
}
});
Util.print(a);
}
|
|
o/p
4 94 9 14 1
9 94 4 14 1 |
|
isnt it similar to what i proposed in one of my posts ?
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
mmgc
Newbie
Gender:
Posts: 47
|
|
Re: Sort array to get max concatinated value
« Reply #8 on: Jun 3rd, 2011, 4:41am » |
Quote Modify
|
on Jun 2nd, 2011, 5:18am, birbal wrote:
isnt it similar to what i proposed in one of my posts ?
|
|
I think the beauty here is the use of quick sort to solve the problem.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Sort array to get max concatinated value
« Reply #9 on: Jun 3rd, 2011, 8:47am » |
Quote Modify
|
It's probably not an optimal way to do it though, because you operate on all characters, rather than on the few that are needed. You don't need to concatenate A and B unless one is the prefix of the other; in other cases plain (reverse) lexicographic order is sufficient.
I suspect a variant of bucket-sort might also work better than quick-sort, due to the nature of the problem. First sort on the first number, then within each group on the second, etc.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
krishnav
Newbie
Posts: 12
|
|
Re: Sort array to get max concatinated value
« Reply #10 on: Dec 25th, 2011, 6:28pm » |
Quote Modify
|
@towr how would you sort between 9 & 94 and again between 1 & 12 using digit at a time sort?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Sort array to get max concatinated value
« Reply #11 on: Dec 26th, 2011, 12:55am » |
Quote Modify
|
It's a bucket sort, so strings with the same starting character are first put in the same bucket, but in the second round (as long as the second character is different) they'll be put in different buckets. You just have to be careful to have a bucket for strings that end at a given position; they're a bit of a special case.
So if we have 9,94,1,12
round 1:
bucket9 [9,94]
bucket1 [1,12]
round 2:
bucket9.e [9]
bucket9.4 [94]
bucket1.2 [12]
bucket1.e [1]
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Sort array to get max concatinated value
« Reply #12 on: Dec 26th, 2011, 10:04am » |
Quote Modify
|
on Dec 26th, 2011, 12:55am, towr wrote:It's a bucket sort, so strings with the same starting character are first put in the same bucket, but in the second round (as long as the second character is different) they'll be put in different buckets. You just have to be careful to have a bucket for strings that end at a given position; they're a bit of a special case.
So if we have 9,94,1,12
round 1:
bucket9 [9,94]
bucket1 [1,12]
round 2:
bucket9.e [9]
bucket9.4 [94]
bucket1.2 [12]
bucket1.e [1]
|
|
I cudn't really understand what are you doing. Can you explain in a bit more detail, how would you arrange final buckets ?
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
krishnav
Newbie
Posts: 12
|
|
Re: Sort array to get max concatinated value
« Reply #13 on: Dec 26th, 2011, 2:01pm » |
Quote Modify
|
@towr I understood the bucket sort part...was curious how the empty digit would compare against a non-empty digit; we clearly cannot come up a fixed rule, such as empty's are greater than non-empty's or vice-versa.
because between 9 & 94, the empty (9) wins over 94.
and between 1 & 12, the non-empty (12) wins over 1.
|
|
IP Logged |
|
|
|
kaka
Newbie
Gender:
Posts: 24
|
|
Re: Sort array to get max concatinated value
« Reply #14 on: Dec 26th, 2011, 5:35pm » |
Quote Modify
|
While comparing empty value, assume it is equal to the left most digit
9 and 94 , assume we are comparing 99 and 94 and rate 9 over 94
1 and 12, assume we are comparing 11 and 12 and rate 12 over 1
Similarly for 832 and 83 , compare 838 and 832
|
| « Last Edit: Dec 26th, 2011, 6:55pm by kaka » |
IP Logged |
|
|
|
carpinteyrojwf
Newbie
Posts: 1
|
|
Why do you want to do it that way?
« Reply #15 on: Dec 26th, 2011, 6:46pm » |
Quote Modify
|
Why do you want to do it that way?
spam link removed --SMQ
|
| « Last Edit: Dec 27th, 2011, 5:47am by SMQ » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print