Function to take a positive integer and return the next bigger number formed by the same digits

Question

I've written a solution to a Codewars challenge:

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

12 ==> 21; 513 ==> 531; 2017 ==> 2071

I am getting the following error on Codewars: "Execution Timed Out (12000 ms)". I am a rookie, and would appreciate if anyone could give me some suggestions on optimizing my code, as this is something I know very little about.

I've made some minor tweaks but nothing that really reconstructs the solution from the ground up.

//takes a num and finds the next biggest num composed of the same digits.

function nextBigger(num) {
  let newNum = 0;
  let otherNum = 0;
  let indicator = 0;
  while (num > newNum) {
    if (indicator === 0) {
      otherNum = num;
      indicator++;
      continue;
    }

    if (
      String(num)
        .split("")
        .sort()
        .join("") ===
      String(otherNum)
        .split("")
        .sort()
        .join("")
    ) {
      if (otherNum > num) {
        newNum = otherNum;
      }
    }

    otherNum++;
  }

  return newNum;
}

Answer 1

I know whatever program codewars uses does not care about readability (most computer programs don't), but in the real world readability is important.

The first step to refactoring should be creating tests. This way you can easily figure out if you've broken something:

let test1 = getNextNumberOfGreaterSize(12);
let test2 = getNextNumberOfGreaterSize(513);
let test3 = getNextNumberOfGreaterSize(2017);

assertEquals(21, test1);
assertEquals(531, test2);
assertEquals(2071, test3);

function assertEquals(expected, actual) {
  if (expected !== actual) {
    throw new Error("expected: " + expected + " but was: " + actual);
  }
}

While designing tests, you may discover other edge cases such as:

• What if the number given is already the highest?
• What if the number doesn't have any other combinations (such as 11)?
• What if a single digit number is given (1)?

You didn't provide a function name but assuming it wasn't descriptive I suggest you change it. It's tricky coming up with a name for such a function (Functions like these probably wouldn't exist in the 'real world'), but something like getNextNumberOfGreaterSize(originalNumber) with a comment describing what it does.

Set otherNumber (Note I changed the name to be more readable. Cutting off 3 letters isn't saving you, or the interpreter any time) outside of the while loop and get rid of your if statement:

let otherNum = originalNumber;
while (originalNumber > newNum) {
if (....

Whatever you are doing inside the if statement deserves a comment. Better yet, you should also put it inside a function (especially when you know you'll refactor it later!):

function numbersContainSameDigits(number1, number2) {
  return String(number1)
        .split("")
        .sort()
        .join("") ===
      String(number2)
        .split("")
        .sort()
        .join("");
}

Now that we got the important stuff out of the way, let's move onto what you're actually asking for. How can we shave a few milliseconds off each run / Why is coderank telling us the methods too slow?

Computers suck at computing Strings. However they rock at computing numbers. Let's see if we can cut down on the amount of String computing.

The way we check if the two numbers contain the same letters can be changed. First we get an array containing the characters, then compare the two arrays after sorting:

function numbersContainSameDigits(number1, number2) {
  return checkIfTwoArraysAreEqual(getArrayContainingDigits(number1), getArrayContainingDigits(number2));
}

function checkIfTwoArraysAreEqual(array1, array2) {
  return JSON.stringify(array1.sort()) === JSON.stringify(array2.sort());
}

function getArrayContainingDigits(number) {
    let arrayOfDigits = [];
    while (number >= 1) {
        arrayOfDigits.push(Math.floor(number % 10));
      number /= 10;
    }

    return arrayOfDigits;
}

Edit:

You are going through a much wider range of numbers than needed. You could instead get all available combinations of a number, and select the permutation 1 index greater than the input.

Answer 2

Stimulating question;

Both the edit of @dustytrash and the comment of @Ry are giving a great hint.

But before we go there, let's look at this part:

  let newNum = 0;
  let otherNum = 0;
  let indicator = 0;
  while (num > newNum) {
    if (indicator === 0) {
      otherNum = num;
      indicator++;
      continue;
    }

You are setting up otherNum up within the loop, you only do it once with indicator but you are still performing an if statement every cycle. You can just drop indicator completely and start with the smallest possible value of otherNum:

  let otherNum = num + 1;
  while (num > newNum) {

Then you can replace this part:

  if (otherNum > num) {
    newNum = otherNum;
  }

with simply a return statement there:

if (String(num).split("").sort().join("") === String(otherNum).split("").sort().join(""){
        return otherNum;
}

You would not need newNum at all any more. Still, to your point in the question, we are looking for more than minor tweaks.

This code basically tries out every integer between num and the solution, that is to say potentially a ton of numbers. For 2017 -> 2071 there are 54 tries, but there are only 24 possible combinations with 4 digits (4*3*2*1). From those 24 possible combinations we know that none of the combinations can start with either 0 or 1 because that would give a number smaller than 2017. Which leaves us with only 12 combinations to test.

To go further, if we want to check the next big number of 2341, we know that the next biggest number starts with either 2 possibly, or 3. I could not be 1 since then the number is too small, it could not be 4 because any number starting with 4 is going to be both greater than any number starting with 3.

Finally, we know that if the next biggest number started with '3', we should just apply the remaining digits from low to high (so 3124), there is no way to make a lower number than that.

This is my rewrite, very commented since I am still wrapping my brains around it a bit, but it seems to work. I made one small change for my benefit, the code returns -1 if it cannot find a bigger number with the same digits.

(Which is another issue with your code, it seems that running it for say 531, it will run forever).

//H4ck: We trust that n is part of the list
function removeNumber(list, n){
  list.splice(list.indexOf(n), 1);
  return list;
}

//Takes a string that looks like a positive integer number 
//and returns the next bigger number formed by the same digits
//Return the same number if we can not find a next bigger number
function nextBiggerString(s){
  
  let digits = s.split('');
  let wip = [...digits]; //Work in progress
    
  //Special case we don't want to deal with, 2 digits
  //Very useful for a recursive approach
  if(digits.length == 2){
    //Don't reverse if we are already at max
    return Math.max(digits.reverse().join(""), s);
  }
  
  //First digit has to be equal or next biggest after target digit to make sense
  const target = digits[0];
  //Only keep valid starting candidates 
  wip = wip.sort().filter(i=>i>target);
  //Very often the solution is option 1, kicking the can down the road
  const option1 = target + nextBiggerString(s.slice(1));
  if(wip.length==0){
    //The first digit was the highest digit of them all, so we can only kick the can
    return option1;
  }else{
    if(option1 != s){
      //Only return option1 is it different from what we started with
      return option1
    } else{
      //Otherwise take the next digit, and sort the rest ascendingly
    	return wip[0] + removeNumber(digits,wip[0]).sort().join('');      
    }   
  }
}

//Takes a positive integer number and returns the next bigger number formed by the same digits
//Return -1 if we cant find a next bigger number
//this uses a stringbased biggerString because this uses an iterative solution
//where for example 034 from 1034 becomes 34, which would return then 143
function nextBigger(n){
  const maybe = nextBiggerString(String(n))*1;
  return maybe == n ? -1 : maybe;
}


console.log(nextBigger(12));
console.log(nextBigger(513));
console.log(nextBigger(531));
console.log(nextBigger(2017));
console.log(nextBigger(2721));