|
| 1 | +//Tricky problem but easy |
| 2 | +//this video was helpful https://www.youtube.com/watch?v=wT7gcXLYoao&ab_channel=takeUforward |
| 3 | + |
| 4 | +classSolution { |
| 5 | +//Time complexity O(N^2) becuase of remove method |
| 6 | +publicStringgetPermutation(intn,intk) { |
| 7 | +StringBuilderkthPerm =newStringBuilder(); |
| 8 | +intfact =1; |
| 9 | +//this list will contain all the values from 1 to n for reference |
| 10 | +ArrayList<Integer>list =newArrayList<>(); |
| 11 | +for (inti =1;i<n;i++) { |
| 12 | +fact =fact*i; |
| 13 | +list.add(i); |
| 14 | + } |
| 15 | +list.add(n); |
| 16 | +k--; |
| 17 | +while (true) { |
| 18 | +kthPerm.append(list.get(k/fact)); |
| 19 | +list.remove(k/fact); |
| 20 | +if (list.size()==0) |
| 21 | +break; |
| 22 | +k =k%fact; |
| 23 | +fact =fact/(list.size()); |
| 24 | + } |
| 25 | +returnkthPerm.toString(); |
| 26 | + } |
| 27 | + |
| 28 | + { |
| 29 | +//Bruteforce solution (gives TLE) similar to Next Permutation problem no.31 |
| 30 | + |
| 31 | +// public String getPermutation(int n, int k) { |
| 32 | +// int[] num = new int[n]; |
| 33 | +// for (int i = 1; i<=n; i++) { |
| 34 | +// num[i-1] = i; |
| 35 | +// } |
| 36 | +// for (int i = 1; i<k; i++) { |
| 37 | +// nextPermutation(num); |
| 38 | +// } |
| 39 | +// return numToString(num); |
| 40 | +// } |
| 41 | + |
| 42 | +// public void nextPermutation(int[] nums) { |
| 43 | +// int pivot = nums.length-1; |
| 44 | +// while (pivot>0 && nums[pivot]<nums[pivot-1]) { |
| 45 | +// pivot--; |
| 46 | +// } |
| 47 | +// pivot--; |
| 48 | +// int j = nums.length-1; |
| 49 | +// while (j>0 && nums[j]<nums[pivot]) { |
| 50 | +// j--; |
| 51 | +// } |
| 52 | +// System.out.println(pivot+" "+j); |
| 53 | +// swap(nums, j, pivot); |
| 54 | +// reverse(nums, pivot+1); |
| 55 | +// } |
| 56 | + |
| 57 | +// public void reverse(int[] num, int start) { |
| 58 | +// int end = num.length-1; |
| 59 | +// while (start<end) { |
| 60 | +// int temp = num[start]; |
| 61 | +// num[start] = num[end]; |
| 62 | +// num[end] = temp; |
| 63 | +// start++; |
| 64 | +// end--; |
| 65 | +// } |
| 66 | +// } |
| 67 | + |
| 68 | +// public void swap(int[] num, int i, int j) { |
| 69 | +// int temp = num[i]; |
| 70 | +// num[i] = num[j]; |
| 71 | +// num[j] = temp; |
| 72 | +// } |
| 73 | + |
| 74 | +// public String numToString(int[] arr) { |
| 75 | +// StringBuilder sb = new StringBuilder(); |
| 76 | +// for (int num: arr) |
| 77 | +// sb.append(num); |
| 78 | +// return sb.toString(); |
| 79 | +// } |
| 80 | + |
| 81 | + } |
| 82 | + |
| 83 | +} |