Skip to content

Instantly share code, notes, and snippets.

@mwcz
Created March 16, 2020 18:46
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save mwcz/ca179ac811e4e7e030c6e26e434f17a8 to your computer and use it in GitHub Desktop.
Save mwcz/ca179ac811e4e7e030c6e26e434f17a8 to your computer and use it in GitHub Desktop.
My solution to codewars "Next bigger number with the same digits" kata
// write array `a` onto array `b` starting at position `p`
function overlay(a, b, p) {
for (let [i, n] of a.entries()) {
b[p+i] = n;
}
return b;
}
// in an array, swap items at indexes i1 and i2
function swap(arr, i1, i2) {
const [a, b] = [arr[i1], arr[i2]];
arr[i1] = b;
arr[i2] = a;
}
/**
* Algorithm:
*
* - move from right to left, one digit (d) at a time
* - for each digit (d), compare it to the digits that follow it (again moving from right to left)
* - if any following digit (f) is found that is greater than (d), swap their positions and break out of all loops
* - sort all the digits that come after (f) (which is now in (d)'s original position)
* - done!
*/
function nextBigger(n){
let digits = n.toString().split('');
for_each_digit:
for (let i = digits.length - 1; i >= 0; --i) {
let d = digits[i];
let lower;
for_each_trailing_digit:
for (let j = digits.length - 1; j > i; --j) {
if (d < digits[j]) {
swap(digits, i, j);
let trailing = digits.slice(i + 1, digits.length);
trailing.sort();
overlay(trailing, digits, i + 1);
break for_each_digit;
}
}
}
let answer = +digits.join('');
return n == answer ? -1 : answer;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment