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

Question:

I made a function that given a number n , 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 must 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 the case of a very large number it must do many comparisons in which:

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

How can you improve the part where you compare if the digits of the number are the same as 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 be something like this, the mechanics are not my invention, but geeksforgeeks 's, 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 to be 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 don't find that number, we return -1.
  • Then, we look in the digits that were left to 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 swap 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 it would be there.
Post Views: 8
Scroll to Top