I think this may work..!!
Sort the input array first, extract each no.s first digit and put them
in another array..
Then compare each element of new array with fist digit of main
array.. and then concatenate the found ones to a string...
eg:if input a[]=34,567,87,98,33,1, new array
sorry, concatenate the found no in the new no rather than putting it
in the new no...
On 8/15/11, Puneet Gautam puneet.nsi...@gmail.com wrote:
I think this may work..!!
Sort the input array first, extract each no.s first digit and put them
in another array..
Then compare each element of
isn't it a simple question of applying radix sort from most significant to
least signigicant digit and concatenating all the sorted numbers to get the
largest number..
On Sat, Aug 13, 2011 at 11:13 PM, Kunal Patil kp101...@gmail.com wrote:
Let me clarify.
Lets take example
53
147
@ankur: No its not radix sort...radix sort would give wrong answer
when the input contains heterogeneous numbered digits in the
array(even when going 4m msd to lsd)...
eg:
32,583,678,1,45,9
Radix sort would give:
9,583,678,45,32,1
whereas the answer has to be:
9,678,543,45,32,1
and hence
why will 678 come after 583 ?
okay ., sort from least to most significant digit. append imaginary 0's at
the end of the numbers with varying length to make them of same length
On Sun, Aug 14, 2011 at 5:54 PM, Puneet Gautam puneet.nsi...@gmail.comwrote:
@ankur: No its not radix sort...radix
Ankur, I agree with your algo.
- radix sort from least significant to most significant.
- a slight modification can be done on the appending 0 part.
when you find the a digit is absent from the number, you leave the number.
e.g
95, 87, 9, 45, 38
one's place, sort: (descending)
9, 38, 87, 95, 45
What about the case 1, 90 ?
It will give 190 as the answer, isn't it?
Or am I getting your algo wrong?
On Sun, Aug 14, 2011 at 11:56 PM, Dipankar Patro dip10c...@gmail.comwrote:
Ankur, I agree with your algo.
- radix sort from least significant to most significant.
- a slight modification
as they havve different number of digits, we append 0 at the end after 1. so
the two numbers are 90,10 . after appending you get 901. Basically , i think
it is lexographic sorting
On Mon, Aug 15, 2011 at 12:05 AM, Kunal Patil kp101...@gmail.com wrote:
What about the case 1, 90 ?
It
@Ankur, what if the numbers are 23 232??
23 add 0 == 230
Since, 232 230 === 232 should come first..
Hence answer: 23223.
However; 23232 is greater..
wutta say? :-/
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion
@yasir is there any solution in these 32 posts ? :D
On Mon, Aug 15, 2011 at 1:34 AM, Yasir yasir@gmail.com wrote:
@Ankur, what if the numbers are 23 232??
23 add 0 == 230
Since, 232 230 === 232 should come first..
Hence answer: 23223.
However; 23232 is greater..
wutta say? :-/
Not Sure! Me too looking for a solution.. :D
So far, Kunal's approach (Convert each string to length max_size where you
append it circularly) seems to be working fine. :-)
..and Chengjie's approach should also work, but the interviewer rejected
this idea saying, he wants a good logic for
@ Kunal:
oh. zero is making some nice test cases. I will have to reconsider the
solution that I provided.
On 15 August 2011 01:53, Yasir yasir@gmail.com wrote:
Not Sure! Me too looking for a solution.. :D
So far, Kunal's approach (Convert each string to length max_size where
you append
Just a qestion, how do you sort lexographically ? that is tha approach that
we will apply here.. .and yes the approach is flawed. will come with a
solution soon..
On Mon, Aug 15, 2011 at 8:42 AM, Dipankar Patro dip10c...@gmail.com wrote:
@ Kunal:
oh. zero is making some nice test cases. I will
@ $: how ll you manage something like this:
2,3,100,90,10
2nd array becomes: 200,300,100,900,100
descendng order: 900,300,200,100,100
how to take care which 100 is of 10 cos we need 10 1st...??
On Aug 13, 1:00 pm, rahul aravind rahularavin...@gmail.com wrote:
awesome alogoritm dave:):)
Following approach should work:
1) Count max number of digit in any integer of input. Let it be m. (Thanks
to dave..)
2) For each int having less than m digits:
Convert it to string of length m where you append circularly.
For e.g. if m=5
53 -- 53535
100 -- 10010
@kunal: seems fine.. tried it on some cases...
On Sat, Aug 13, 2011 at 5:17 PM, Kunal Patil kp101...@gmail.com wrote:
Following approach should work:
1) Count max number of digit in any integer of input. Let it be m. (Thanks
to dave..)
2) For each int having less than m digits:
@kunal: what is the best way to implement step 2?
On Sat, Aug 13, 2011 at 7:33 PM, Ashish Sachdeva ashish.asachd...@gmail.com
wrote:
@kunal: seems fine.. tried it on some cases...
On Sat, Aug 13, 2011 at 5:17 PM, Kunal Patil kp101...@gmail.com wrote:
Following approach should work:
1)
I dont know whether this is best approach to do step 2 or not. But it's
certainly good.
//I will show for two strings s1 and s2
len1 = s1.length();
len2 = s2.length();
ind1 = 0; //Index in the first string
ind2 = 0; //Index in the second string
while( ind1len1 || ind2 len2 ) //Match until
@ kunal : arent we supposed to construct the string fr each number equal to
the max length of any number...
whr r v doing dat chking in dis algo?
On Sat, Aug 13, 2011 at 10:25 PM, Kunal Patil kp101...@gmail.com wrote:
I dont know whether this is best approach to do step 2 or not. But it's
Let me clarify.
Lets take example
53
147
1471470
As per algo:
sort 5353535 , 1471471 and 1471470 lexicographically to get answer.
But You are not going to compare all these simultaneously.
Might be you will first compare 53 and 147 for lexicographical order. In
this case you are not required to
@Yasir: I think the following will work. Counterexamples welcome.
Find the number of digits in each of the integers, and find the max of
that number, say m.
Fill a second array as follows: If the ith integer has m digits, copy
it into the second array. If the ith number has less than m digits,
@dave,
Awesome approach. It was really tough to find a counter example. :D
1st number: 23
2nd number: 23235
Applying ur algo:
23 - 2
-- 23235
Answer using ur algo: 2323235
However the correct answer should be: 2323523
Am I missing something in the above example? :-/
--
You
22 matches
Mail list logo