Interview Question

Software Engineering Intern Interview

Given a number n, find the largest number just smaller than

  n that can be formed using the same digits as n.

Interview Answer

2 Answers


I gave the obvious solution of generating all permutations of the number n and ordering them, find the one that occurs before n.
Then I figured out that if I sort the digits from a certain point onwards into increasing order, it can help me build up to the solution. I proposed my algorithm and we began doing some really sort of pseudofunctional java code that solved the problem. After the end of that, I analyzed my solution and found it to run in O(n^2) time utilizing a bucket sort for the sorting operation. This was a big improvement from O(n!) but still not optimum. He explained the optimum solution found a pivot at which point it sorted the digits, running in O(n).

Interview Candidate on Apr 17, 2014

For this question you can keep an array of 0-9

Start traversing from back, if any bucket before that is fill that is you encountered an element smaller than it then put that element in current position and place all remaning elements in decreasing order.

For example say the no is 10987598023

start from 3
A = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
array after 3 becomes [0, 0, 0, 1, 0,..]

then when u see 2, you see that no smaller element. Array becomes
[0, 0, 1, 1, 0,...]

now when u reach at 0, again no smaller element, so array becomes
[1, 0, 1, 1, 0, ...]

Now when u reach 8 the just smaller element is 3

So, replace 8 with 3 and the array becomes [1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0]

So the number just smaller is 10987593820. O(n)

Srikant Aggarwal on Oct 24, 2014

Add Answers or Comments

To comment on this, Sign In or Sign Up.