3
\$\begingroup\$

I'm trying to solve this challenge, which consists of finding the next biggest number formed by the digits of the passed in number. If it is impossible to find a number larger than the passed in parameter by rearranging the digits, return -1.

EX: nextBigger(12) === 21
    nextBigger(2017) === 2071
    nextBigger(987654321) === -1

My solution works, but they are testing a bunch of really long numbers that are causing it to time out. I don't even get to see what these really long numbers are because it times out and doesn't return any test cases. I was wondering what could be done to optimize this further.

function nextBigger(n){

      let numString = n.toString();
      let permutations = []
      let smallest = numString[0];
      let descending = true;
      let same = true;

      for(let i = 1; i < numString.length;i++){
        if(numString[i-1] < numString[i]){
            descending = false;
        }
        if(numString[i-1] != numString[i]){
            same = false;
        }

        if(smallest > numString[i]){
          smallest = numString[i]
        }
      }
      if(descending || same){
        return -1;
      } 

      const permute = (prefix, str) => {
        let index = String(str).length;
        if(index == 1){
          permutations.push( prefix + str );
        }

        for(let i = 0; i < index; i++){
          permute(prefix + str[i], str.slice(0,i) + str.slice(i+1,index))
        }
      }


      let nextBiggest = Infinity;
      for(let i = numString.length - 2; i >= 0; i--){
          let start = numString.slice(0,i);
          let end = numString.slice(i,numString.length)
          permute(start,end)
          for(let j = 0; j < permutations.length; j++){
            if(permutations[j] > n && permutations[j] < nextBiggest){
              nextBiggest = permutations[j];
            } 
          }
          if(smallest == numString[i]){
            return nextBiggest
          }
          permutations = [];
      }
      return -1
    }


    console.log(nextBigger(28554))
    //42558
    console.log(nextBigger(1961821))
    //1962118
    console.log(nextBigger(12))
    //21
    console.log(nextBigger(1111))
    //-1
    console.log(nextBigger(987654321))
    //-1
\$\endgroup\$
  • \$\begingroup\$ Make your question self contained regarding the coding problem here, instead of just providing a link please. \$\endgroup\$ – πάντα ῥεῖ Jan 10 '17 at 20:20
  • \$\begingroup\$ I've added the required info. Let me know if I should add anything else. \$\endgroup\$ – Tom Pridham Jan 10 '17 at 20:30
  • \$\begingroup\$ Did you try console.log(nextBigger(1211)) ? \$\endgroup\$ – ChatterOne Jan 11 '17 at 11:39
  • \$\begingroup\$ Just a side note. If they are using V8 to run the code you should avoid using for(let i... as V8 wraps the for loop in a do not optimise flag if you declare a block scoped variable in one of the for statements. Use vars it will improve performance on V8, though for everything but the for loop the improvement is marginal. \$\endgroup\$ – Blindman67 Jan 11 '17 at 14:45
  • \$\begingroup\$ The problem is in your algorithm, need to use a better solution : stackoverflow.com/questions/9368205/… \$\endgroup\$ – juvian Jan 11 '17 at 17:56
1
\$\begingroup\$

I'm not entirely sure what this code does, but it certainly seems too long for the problem. First some general review:

      let numString = n.toString();

This is a matter where opinions will certainly differ, but I would prefer to instead assign n = n.toString(); as n is never used again, and the real purpose of this line is to coerce the input to the type which you want to receive.

      let permutations = []

This is a bit surprising: you only need to generate one permutation, so why do you need an array with many? A comment explaining the purpose would be nice.

      let smallest = numString[0];

This is also surprising. "Smallest" in what sense? It's unlikely that the smallest digit will coincidentally be the first one.

      if(descending || same){
        return -1;
      } 

Is there any reason for using two variables here? I think it could be simplified by having one variable which tracks whether there's any increase over the previous digit (although the complete rewrite will eliminate this anyway).

      const permute = (prefix, str) => {

What does this function do? Comment!

        let index = String(str).length;

Earlier the code used toString(); here it uses String(...) to do the same thing. Be consistent.

        if(index == 1){

Although index will always be a number, consistently using === reduces the cognitive load in working out whether == should really have been ===.

      let nextBiggest = Infinity;

WTF? This method was working with strings: where does Infinity come into it?

      return -1

This should be unreachable, so why not throw an exception to alert you to the fact that if it's reached you have a bug?


Now, the part you're really interested in. The algorithm.

The question of finding the next permutation in lexicographic order is a classical one (going back 7 centuries) and well documented in the literature. E.g. Wikipedia gives the following algorithm:

  1. Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.
  2. Find the largest index l greater than k such that a[k] < a[l].
  3. Swap the value of a[k] with that of a[l].
  4. Reverse the sequence from a[k + 1] up to and including the final element a[n].
\$\endgroup\$
  • \$\begingroup\$ Since you have written an extensive review, you may also want to point out the bug that I talked about in the other comment: console.log(nextBigger(1211)) outputs Infinity instead of 2111. \$\endgroup\$ – ChatterOne Jan 11 '17 at 15:54
0
\$\begingroup\$

Javascript is a lot better at handling numbers than strings. Though I am not sure of the range of numbers that the problem will present. If they fall outside the precision of Javascripts double (Number) then you will need to use strings.

If not then the following will improve the performance significantly by working with numbers rather than strings.

function nextBigger(n){
    var dig = []; // holds digits lowest first
    var pow = []; // holds powers 1,10,100,1000,...
    var num = []; // holds dig at power ie dig[i] * pow[i]
    var p = 1;  // current power
    var nn = n;  // copy of number
    var d;       // current digit
    var lastD =-1;  // last digit 
    var i = 0;      // current array index;
    var assending = true;  // true if no solution
    while(nn> 0){   // get each digit and test for assending
        d = nn % 10;  // get the digit
        if(d < lastD){  // is it smaller
            assending = false
        }
        pow[i] = p;  // set the power
        num[i] = p * d;  // set the dig times power
        lastD = dig[i++] = d;  // set the dig in array 
        nn = Math.floor(nn/10);  // reduce number for next digit
        p *= 10;  // get next power
    }
    if(assending){  // early exit
        return -1;
    }
    if(i === 2){  // quick early exit if 2 digit
        return dig[0] * 10 + dig[1];
    }
    var len = i; // set the length to number of digits found
    var cn;  // current number
    cn = nn = n;  
    var np; // Next permutation 
    var min = Infinity; // current min
    var d,p;  // digit and power
    var si,sj;  // swap indexes
    while(len > 0){
        si = -1; // flag no swap
        for(i = 0; i < len; i ++){
            d = dig[i];  // get digit
            p = pow[i];  // and its power
            nn = cn - num[i];  // remove it from the current number
            for(j = 0; j  < len; j ++){  // for all the othe digits
                if(i !== j ){  // not in the same position
                    // swap the digits
                    np = nn - num[j] + (pow[j] * d) + (p * dig[j]);
                    // is the next permutation less than the current min and greater than number
                    if(np < min && np > n ){
                        min = np; // set the new min
                        si = i;   // digits to swap
                        sj = j;
                    }
                }
            }
        }
        if(si !== -1){ // were digits swapped
            var t = dig[si];  // swap the digits in the array
            num[si] = (dig[si] = dig[sj]) * pow[si];
            num[sj] = (dig[sj] = t) * pow[sj];
            cn = min; // set the new value to test
        }
        len -= 1;
    }
    return min

}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.