## DEV Community

Flavio De Stefano

Posted on • Updated on

# Kata resolution: Next bigger number with the same digits

I would like to share with you my solution of a Kata on CodeWars.

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 and I just started writing random numbers.

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 has 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 of 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.

``````For number 21581957621
2158195 <-- here --> 7621
``````

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:

``````function nextBigger(n){
var d = n.toString().split('');

// find the pivot, the point (from right) where i > i-1
var p = -1;
for (var i = d.length-1; i > 0; i--) {
if (+d[i] > +d[i-1]) {
p = i-1;
break;
}
}

// if we are unable to find the pivot, skip
if (p == -1) return p;

// splice the digits in the pivot
var right = d.splice(p);

// extract pivot
var pv = right.splice(0, 1);

// find the lowest number > pv
var mm = null, mmi = null;
for (var i = 0; i < right.length; i++) {
if (right[i] > pv) {
if (mm == null || right[i] < mm) {
mm = right[i];
mmi = i;
}
}
}

if (mmi == null) return -1;

right.splice(mmi, 1);
right.push(pv);
right = right.sort();

// concat the left + new pivot + right part
var ret = +d.concat([mm]).concat(right).join('');
if (ret < n) return -1;

return ret;
}
`````` Kotlin ;)

My solution:

``````fun myNextBiggerNumber(n: Long): Long {
if (n < 0) return -1
var myPivot = 0
var beforePivot = ""
var afterPivot = ""
val digitList = n.toString().map { it.toString().toInt() }.toMutableList()
for (pos in digitList.lastIndex downTo 0) {
if (pos > 0) {
if (digitList[pos] > digitList[pos - 1]) {
myPivot = digitList[pos - 1]
beforePivot = n.toString().substring(0, pos - 1)
afterPivot = n.toString().substring(pos)
break
} else if (digitList[pos] < digitList[pos - 1] && pos == digitList.lastIndex) {
continue
}
}
}

val smallLarger = findSmallLarger(afterPivot, myPivot)

val newAfterString = if (afterPivot.length > 1) {
StringBuilder(afterPivot).append(myPivot.toString()).removeRange(
smallLarger.second, smallLarger.second + 1
).toString().split("").sorted().joinToString("")
} else {
StringBuilder(afterPivot).append(myPivot.toString()).toString()
}

val solution = if (beforePivot.isEmpty()) {
"\${smallLarger.first}\$newAfterString".toLong()
} else if (smallLarger.first.isEmpty()) {
"\$beforePivot\$newAfterString".toLong()
} else {
"\$beforePivot\${smallLarger.first}\$newAfterString".toLong()
}

return if (solution > 0L) solution else -1
}

fun findSmallLarger(afterPivot: String, myPivot: Int): Pair<String, Int> {
var mySmallLarger = ""
var mySmallLargerPos = 0
val digitList = afterPivot.map { it.toString().toInt() }.toMutableList()

if (afterPivot.length > 1) {
for (pos in digitList.lastIndex downTo 0) {
if (digitList[pos] > myPivot) {
mySmallLargerPos = pos
mySmallLarger = digitList[pos].toString()
break
}
}
}
return Pair(mySmallLarger, mySmallLargerPos)
}

``````

Code wars better solution (by akvptp, akvosir):

``````fun nextBiggerNumber(n: Long): Long {
val text = n.toString().toMutableList()
for (i in text.size - 2 downTo 0) {
if (text[i] < text[i + 1]) {
val tail = text.subList(i + 1, text.size)
val min = tail.withIndex().filter { it.value > text[i] }.minBy { it.value }!!
text[i + 1 + min.index] = text[i]
text[i] = min.value
tail.sort()
return text.joinToString("").toLong()
}
}
return -1
}
`````` Hannah Jones

I found this really helpful, thanks! I used your algorithm to develop my own solution in C#...

``````using System.Collections.Generic;
using System;
using System.Linq;

public class Kata
{
public static long NextBiggerNumber(long n)
{
List<long> digitList = ConvertNumberToList(n);

int pivotIndex = -1;
bool pivotFound = false;

for(int index = digitList.Count - 1; index > 0; index -= 1){
if (pivotFound == false && digitList[index] > digitList[index - 1]){
pivotIndex = index - 1;
pivotFound = true;
}
}

if(!pivotFound || pivotIndex == -1) {return -1;}

int pivot = Convert.ToInt32(digitList[pivotIndex]);

List<long> left = new List<long>();
left = digitList.GetRange(0, pivotIndex);

List<long> right = new List<long>();
int count = (digitList.Count - pivotIndex) - 1;
right = digitList.GetRange(pivotIndex + 1, count);

List<long> rightDigitsBiggerThanPivot = new List<long>();

foreach (long number in right){
if (number > pivot){
}
}

if (rightDigitsBiggerThanPivot.Count == 0){
return -1;
}

long pivotSub = rightDigitsBiggerThanPivot.AsQueryable().Min();

right.Remove(pivotSub);
right.Sort();

string ret = "";

foreach (var number in left){
ret = ret + number.ToString();
}

ret = ret + pivotSub.ToString();

foreach (long val in right){
ret = ret + val.ToString();
}

return Convert.ToInt64(ret);
}

public static List<long> ConvertNumberToList(long n)
{
List<long> digits = new List<long>();
string stringN = n.ToString();
foreach (var d in stringN)
{