Project Euler #24: Lexicographic permutations

Question

A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:

012   021   102   120   201   210

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

Answer : 2783915460

Hacker Rank Problem

Solution

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82

import java.util.*; public class Solution { private static char c = 'm'; private static int array_length = c - 'a' + 1; private static char[] cArray = new char[array_length]; static { char ch = 'a'; int i = 0; while (ch <= c) { cArray[i++] = ch++; } } public static void main(String[] args) { Scanner in = new Scanner(System.in); int t = in.nextInt(); while (t-- > 0) { long l = in.nextLong(); System.out.println(getResult(l - 1)); } in.close(); } /** * * @param n * @return */ private static String getResult(long n) { List<Integer> permutations = getPermutations(n); int size = permutations.size(); char[] result = new char[array_length]; int k = 0; //not affected for (int i = 0; i < array_length - size; i++) { result[k++] = cArray[i]; } //permutation List<Character> listAffected = new ArrayList<>(); for (int j = array_length - size; j < array_length; j++) { listAffected.add(cArray[j]); } for (int m = size - 1; m >= 0; m--) { int index = permutations.get(m); result[k++] = listAffected.remove(index); } return new String(result); } /** * In this article, a factorial number representation will be flagged by a * subscript "!", so for instance 341010! stands for 354413021100, whose value * is = 3×5! + 4×4! + 1×3! + 0×2! + 1×1! + 0×0! = ((((3×5 + 4)×4 + 1)×3 + 0)×2 + * 1)×1 + 0 = 463. For example, 46310 can be transformed into a factorial * representation by these successive divisions: * * 463 ÷ 1 = 463, remainder 0 * 463 ÷ 2 = 231, remainder 1 * 231 ÷ 3 = 77, remainder 0 * 77 ÷ 4 = 19, remainder 1 * 19 ÷ 5 = 3, remainder 4 * 3 ÷ 6 = 0, remainder 3 */ private static List<Integer> getPermutations(long n) { List<Integer> list = new ArrayList<>(); int i = 1; while (true) { long quotient = n / i; long remainder = n % i; list.add((int)remainder); if (quotient == 0) { break; } n = quotient; i++; } return list; } }