DEV Community

Flavio Maria De Stefano
Flavio Maria De Stefano

Posted on • Updated on

Kata resolution: Next bigger number with the same digits

#codewars #javascript

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('');
}
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

Join the parts 

215819 + 6 + 1257 = 21581961257
Enter fullscreen mode Exit fullscreen mode

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)[0];

  // 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;
}
Enter fullscreen mode Exit fullscreen mode

Top comments (3)

Collapse
 
licaro1 profile image
licaro-1 •

My solution on python:

def next_bigger(n):
    """Search the next bigger integer."""
    if not n or n < 0:
        return -1
    lst = [x for x in str(n)]
    k = len(lst) - 1
    left, p, right = [], [], []
    for i in range(k, 0, -1):
        #get left, right side and pivot
        if lst[i-1] <  lst[i]:
            right = lst[i:]
            p.append(lst[i-1])
            left = lst[:i-1]
            break
    if len(right) == 1:
        #if in right side we have 1 number, swap places p and right side
        return int(''.join([x for x in left + right + p]))
    right = sorted(right)
    for i in range(len(right)):
        # search the minimum number that is greater p and swap
        if right[i] > p[0]:
            right[i], p[0] = p[0], right[i]
            break
    if not left and not right:
        return -1
    return int(''.join([x for x in left + p + right]))
Enter fullscreen mode Exit fullscreen mode
Collapse
 
crismaver1993 profile image
Cristofer Marín •

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)
}
Enter fullscreen mode Exit fullscreen mode

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
}
Enter fullscreen mode Exit fullscreen mode
Collapse
 
hannah_jones profile image
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){
        rightDigitsBiggerThanPivot.Add(number);
      }
    }

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

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

    right.Add(pivot);
    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)
    {
      long digitToAdd = long.Parse(d.ToString());
      digits.Add(digitToAdd);
    }
    return digits;
    }
}
Enter fullscreen mode Exit fullscreen mode

I am a beginner so open to any suggestions for improvement :)

Read next

chrissiku profile image

Update and delete records on a DWN

Chris Siku -

chrissiku profile image

Connect to Web5 and on a DWN in Web5

Chris Siku -

chrissiku profile image

Query and Read records on a DWN

Chris Siku -

mnkow profile image

From Monolith to Monorepo: A Next.js Migration Story

Michal Kowalkowski -