[algogeeks] Re: largest Number Smaller Than Given Number

Mon, 27 Feb 2006 22:42:23 -0800

@milochen
Your approach is not correct. I am giving a counter example

say our input is
423, so by ur approach the solution is 243 or 234
but the correct answer is 342.

The approach given by dhyanesh and  dazi is correct.

On 2/28/06, milochen <[EMAIL PROTECTED]> wrote:

Does it always have the solution?
What about that 123456789 ?

I think that it doesn't always have solution for all case.

I am sorry that I couldn't give you a C++ code ,
since I have no complier,so I couldn't ensure whether
the code will be compile successful.

Assume  X=(x_1,x_2,x_3, ...,x_(n-2), x_(n-1), x_n) is
our instance s.t. Y=(y_1,y_2,y_3,...,y_(n-2), y_(n-1),y_n)
is the solution for X.
from n-1 to 1, we suppose i is the first i s.t. x_i > x_(i+1)

then the solution is almost like the followng
Y
=(y_1,y_2,y_3,...,y_(n-2), y_(n-1),y_n)
=
(x_1,x_2,x_3,...,x_(i-3),x_(i-2),
x_(i-1),x_(i+1),x_i, x_(i+2),x_(i+3)...
...x_(n-2),x_(n-1),x_n )

To pay attension for that
we just need to do one time swap to get
the solution.

From n-1 to 1, If you cannot find the
first i s.t. x_i > x_(i+1), then the instance X
have no solution.

http://ajay.mishra19.googlepages.com
IIT KGP
--~--~---------~--~----~------------~-------~--~----~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---

Reply via email to