Home / Questions / 298834
Accepted
RazerJs
Asked: 2020-10-07 15:01:59 +0800 CST 2020-10-07 15:01:59 +0800 CST

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

  • 772

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 1until 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));

javascript

4 Answers

  1. Best Answer

    The function should be something like this, the mechanics is 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 added infinityalways 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 lastIndexOfdoes not seem to be the best way to search 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.
    • 4

  2. What I think you can do is get the largest number that can be formed with the numbers by decomposing and ordering the digits of the number. If nit is equal to the number then a larger number can no longer be formed, and you return -1:

    var v2 = n.toString().split('').sort((a, b) => b - a);
if (n == v2.join(''))
    return -1

    If the number is not yet the largest, then you decompose it into another vector (you can't use the first one because it's already ordered) and rotate its digits starting from the end, first you change the last one with the penultimate one, if it's not bigger you go back to change the penultimate with the penultimate and so on until you get a larger number:

    var v = n.toString().split('');
i = v.length - 1;
do {
    //en esta parte intercambio el valor de v[i] con el de v[i-1]
    //sin ayuda de una variable auxiliar
    v[i] = v[i - 1] * 1 + v[i] * 1;
    v[i - 1] = v[i] * 1 - v[i - 1] * 1;
    v[i] = v[i] * 1 - v[i - 1] * 1;
    i--;      
} while(v.join('') <= n);
    return v.join('');

    And the code at the end would look like this:

    function nextBigger(n) {
    var v2 = n.toString().split('').sort((a, b) => b - a);
    if (n == v2.join(''))
        return -1
    
    var v = n.toString().split('');
    i = v.length - 1;
    do {
      v[i] = v[i - 1] * 1 + v[i] * 1;
      v[i - 1] = v[i] * 1 - v[i - 1] * 1;
      v[i] = v[i] * 1 - v[i - 1] * 1;
      i--;      
    } while(v.join('') <= n);
    return v.join('');
}

console.log(nextBigger(5));
console.log(nextBigger(321));
console.log(nextBigger(513));
console.log(nextBigger(9219));
console.log(nextBigger(123));
console.log(nextBigger(2063));
console.log(nextBigger(1497));

    As far as testing goes, it works fine.

    • 3

  3. Finding the largest possible number with certain digits is as simple as ordering the numbers from largest to smallest:

    const input = document.querySelector('#value');
const out= document.querySelector('#response');

input.addEventListener('keyup', function () {
  out.value= input.value.split('').sort((a,b)=> (+b)-(+a)).join('');
});
    <input id="value"/>
<input id="response" />

    But what we want is to make the change to find the minimum greater number , with which we will have to see what numbers must be exchanged, from the units with the tens onwards:

    Given an n-digit number, the digit in position n-1 is the units.

    • If the number in the tens (n-2) is smaller, exchanging it works for us.

      1123 -> 1132

    • If not, we proceed to compare with hundreds... but now we have to reorder the numbers that are on the right from least to greatest

      1132 -> 1231

    • If not, we proceed to compare with thousands... and the same thing happens to us, we have to reorder the remaining numbers:

      21321 -> 22113

    Therefore, we already see a pattern: try to put a larger digit in a column than the unit, leaving the numbers to the left untouched and to the right ordered from smallest to largest:

    let numeros=[
  '100032321', //100033122
  4321,  // -1
  12,    //21
  899999, //989999
  '9786543210000', //9800001234567
  '59884848459853', //5988 48484 83559
  4537530,
  98083994
];

function siguiente(n) {
  //Por si nos pasan un número, nos aseguramos que trabajamos con un string
  n = String(n).split(''); 
  let i = 1;
  while( (+n[n.length - i]) <= (+n[n.length - (i + 1)]) && i < n.length) {  
    i++;
  }
  
  if (i >= n.length) {
    return -1;
  }
  i++;
  const izq = n.slice(0,n.length - i); // se quedará igual
  const der = n.slice(n.length - i);
  const first = der.shift(); //sacamos el elemento a mover
  der.sort((a,b) => a - b); //ordenamos
  //encontramos el más pequeño mayor que el elemento a mover
  const indexNewFirst = der.findIndex(a => +a > +first); 
  //los intercambiamos
  const newFirst = der[indexNewFirst];
  der[indexNewFirst] = first;
  
  return izq.concat(newFirst, der).join('');
}

console.log(numeros.map(siguiente));

    As you can see, the execution is immediate even for very large numbers because it works with character arrays, ordering them, so the complexity is n(Log n) where n is the number of digits

    • 3

  4. I had deleted my previous answer because I wasn't near a computer to fix it and the results were wrong. Here I leave you a new solution, which now analyzing @PabloLozano's code does practically the same thing and looking at his implementation, it is most likely that his is more efficient than the one I am giving you.

    Either way, I think either solution could pass your test, because they have much lower complexity than placing nested loops.

    const nextBigger = (n) => {
  
  const array = `${n}`.split('');
  let big = 0;
  let index;

  for (index = array.length - 1; index >= 0; index--) {
    if (array[index] < big) break;
    big = array[index];
  }

  if (index < 0) return -1;

  const last = array.slice(index);
  
  const next = last.reduce((a, d, i) => {
    if ((d < a[0] && d > last[0]) || d > a[0]) a = [d, i];
    return a;
  }, [last[0], 0]);
  
  [last[0], last[next[1]]] = [last[next[1]], last[0]];
  
  return +[...array.slice(0, index), last[0], ...last.slice(1).sort()].join('');

};

const tests = [513, 2017, 987654321, 414, 1234, 4235, 4321, 69510, 1234567908, 37546227, 59884848459853, 4537530, 98083994];

tests.forEach(n => console.log(`${n} => ${ nextBigger(n) }`));

    • 1