"Next bigger number with the same digits"- Execution Timed Out (16000 ms) - Codewars

Viewed 125

I wrote a program that returns next bigger number created with the same digits, but it looks like code isn't fast enough to be able to pass the random tests, and gives "Execution Timed Out (16000 ms)" error.

public static String swap(String a, int i, int j)
{
    char temp;
    char[] charArray = a.toCharArray();
    temp = charArray[i] ;
    charArray[i] = charArray[j];
    charArray[j] = temp;
    return String.valueOf(charArray);
}

public static void getPermutations(String str, int l, int r, List<Long> permutations ) {
    if (l == r)
        permutations.add(Long.valueOf(str));
    else {
        for (int i = l; i <= r; i++) {
            str = swap(str, l, i);
            getPermutations(str, l + 1, r, permutations);
            str = swap(str, l, i);
        }
    }
}

public static long nextBiggerNumber(long n) {
    String numberTostring = Long.toString(n);

    List<Long> permutations = new ArrayList<>();
    getPermutations(numberTostring, 0 ,numberTostring.length() - 1, permutations);
    permutations.sort(Comparator.naturalOrder());

    for (long number : permutations) {
        if (number > n)  {
            return number;
        }
    }

    return -1;
}

Do you know how to improve this code?

1 Answers

A long can have up to 19 decimal digits, so there are 19! = 121645100408832000 (about 10^17) possible permutations. In reality there are fewer, because some digits will occur more than once; but even then, this is a far too large number for a single computer to process.

I won't solve the puzzle for you, but here's a hint: usually the next biggest number looks very similar to the original one. Look at a few examples (create more if you need to):

  • 312 → 321
  • 26478 -> 26487
  • 9378456923475 -> 9378456923547

Can you find a way to permute the input number only once to end up at the next bigger one?

Related