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.