Kata resolution: Next bigger number with the same digits

This is my first story on Medium, and I would like to share with you my solution of a Kata on CodeWars.

CodeWars is a website where you have to solve “scholastic” problems using programming: for me it is a fantastic method to learn new programming languages and to open up my mind, especially when these problems require new skills and the application of new mind patterns.

I simply love it!

This is the link to the kata problem: http://www.codewars.com/kata/next-bigger-number-with-the-same-digits

I solved it using Javascript, but the algorithm I created is (of course) extendable to all other programming languages.

The problem

You have to create a function that takes a positive integer number and returns the next bigger number formed by the same digits.

So, just to be clear, let me give you some examples:

  1. next bigger of 12 is 21
  2. next bigger of 513 is 531
  3. next bigger of 2017 is 2071
  4. next bigger of 59884848459853 is 59884848483559

If no bigger number can be composed using those digits, you have to return -1.

How I approached

Initially, I totally misunderstood the problem, thinking that I should find the biggest number of the same digits… so I simply wrote:

function nextBigger(n) {
return +String(n).split('').sort().reverse().join('');
}

It would be all too easy.

Therefore, I took paper & pencil (I don’t know if this is the right translation of “ho preso carta e penna”) and I just started writing random numbers.

21581957621

I watched for 2–3 minutes, and I realized that:

  1. there is a left part that must be the same (because we want the next bigger number).
  2. there is a right part that have to change, sorting it.
  3. there is a pivot that is between the two parts and it just increments the number to reach the next.

So, the algorithm consists in three parts.

Find the pivot and split the parts

To find the pivot, we read the number from right to left, until we find a digit that is bigger than the previous one.

21581957621 ←

In this case 5 is the pivot, because 7 > 5

The left part is 215819, the right part is 7621.

Find the substitute for the pivot

What is our substitute for the pivot?

It’s pretty simple, remember that we want the next bigger number, so we have to find the smallest digit (in the right part) that is larger than the pivot.

In this case, 6 is our substitute.

Reorder the right part

Now, to obtain the smallest number, we just reorder the right part, only after inserting our excluded pivot (5) and remove the substitute (6).

7621+5-6 = 7215 → reorder → 1257

Join the parts

215819 + 6 + 1257 = 21581961257

And that’s all!

The Javascript code

The best part is obviously the algorithm, but, here the code I wrote: