loknathsudhakar
BAN USERSo time complexity will be: O(n)
where n is the number of words in the dictionary.
Is that correct?
No..the output should be: [1,8,3,5,4,2,6,0,7]
- loknathsudhakar February 18, 2013@guru:
Take array: [3,2,4,5,1,0,6,8,7]
Idle output: [1,8,3,5,4,26,0,7]
But if my understanding is correct according to you...
Initially sort: [0,1,2,3,4,5,6,7,8] and then swap odd position elements...
output: [0,7,2,5,4,3,6,1,8]
tell me if I am wrong...
Well in that case we have to compare the resulting numbers and take the largest...
- loknathsudhakar February 17, 2013Here we have to sort the numbers according to the digit positions...If conflict occurs between any 2 numbers sort according to the next digit.
Let me explain with an example:
Array: [9, 18, 3, 28, 173]
Step 1: Sort according to 1st digit : [9,3,28,(18,173)]
step 2: here 18, 173 have same 1st digit. So sort according to next digit. : [9, 3, 28, 18, 173]
So output: 932818173...
P.S: We can use 'Divide by 10' technique to get first digit each time.
That may not work....
Bcz relative positions of the individual strings may be changed...
Eg. array [3, 71, 2]
Idle Output: 7132
But your logic produces 7321
Take all even positions into one array and odd positions in to 2nd array... O(n)
Apply any good sorting algorithm for both arrays... O(nlogn)
merge them... O(n)
soo overall time complexity would be: O(nlogn)
How can TC be O(n)....its actually O(n logn) as in each iteration heap sort takes O(nlogn) time complexity.
- loknathsudhakar May 08, 2013