javascript – Improve timing of this function to find the next largest integer with the same digits

Question:

I made a function that given a number n , it takes its digits and looks for the next number greater than it that can be formed with them.

Examples:

n = 513  => debe devolver 531 
n = 9219 => debe devolver 9291  
n = 123  => debe devolver 132

If the number cannot be formed, the function should return -1 . The problem is that this simple function is brute force and does not pass the speed test, because what it does is increase the number by 1 until it finds a number that has the same digits and in case of a very large number it must make many comparisons in which:

  • transform the number
  • runs it
  • order it
  • etc…

How can you improve the part where you compare if the digits of the number are the same as those of the number n ?

function nextBigger(n) {
    const digitos = `${n}`.split('').sort((a, b) => a - b).join('');
    if (n == mayorPosible) return -1
    else {
        do {
            n++
        } while (digitosNumero(n) != digitos)
    }
    return n
}

function mayorPosible(n) {
    return Number(`${n}`.split('').sort((a, b) => b - a).join(''))
}

function digitosNumero(n) {
    return `${n}`.split('').sort((a, b) => a - b).join('')
}

console.log(nextBigger(513));
console.log(nextBigger(2063));
console.log(nextBigger(1497));

Answer:

The function should look something like this, the mechanics are not my invention, but geeksforgeeks' , the implementation is mine, and there are many things that can be improved:

function nextBigger(num) {

    let it = [Infinity,...`${num}`];

    for (let i = it.length - 1; i > 0; i--) {
        if (it[i] < it[i + 1]) {
            let temp = it[i];
            let sub = it.slice(i + 1, it.length).sort((a, b) => a - b);

            let idxSwap = i;

            for (let j = 0; j < sub.length; j++) {
                if (sub[j] > temp) {
                    idxSwap = it.lastIndexOf(sub[j]);
                    break;
                }
            }

            it[i] = it[idxSwap];
            it[idxSwap] = temp;
            it = [...it.slice(0, i + 1), ...it.slice(i + 1, it.length).sort((a, b) => a - b)];
            return +it.slice(1,it.length).join("");
        }
    }

    return -1;
}

console.log(144, nextBigger(144));
console.log(12, nextBigger(12));
console.log(736, nextBigger(736));
console.log(27,nextBigger(27));
console.log(17,nextBigger(17));
console.log(46, nextBigger(46));
console.log(160, nextBigger(160));
console.log(50904, nextBigger(50904));
console.log(9999, nextBigger(9999));
console.log(513, nextBigger(513));
console.log(9219,nextBigger(9219));
console.log(123,nextBigger(123));
console.log(20141, nextBigger(20141));
console.log(1308686, nextBigger(1308686));
console.log(1234567890, nextBigger(1234567890));
console.log(59884848459853,nextBigger(59884848459853));

I always added infinity as the first element because I couldn't find a better way to solve the issue of checking if the first element needs to be moved. The lastIndexOf doesn't seem like the best way to look up the index.

The steps should be:

  • We search from the left until we find the first digit that is less than the previous one, if the input is 534976 we stop at 4 because 4 is less than the next one, which would be 9, if we do not find that number, we return -1.
  • Then, we look in the digits that were on the right for the smallest digit greater than the one we found at the beginning, 976 in the example and the smallest but greater than 4 is 6.
  • We exchange the positions of those numbers, leaving 536974 in the example.
  • From the position of the first digit found at the end, we order it from smallest to largest and that would be it.
Scroll to Top