Project Euler #33: Digit canceling fractions

Question

The fraction ⁴⁹/₉₈ is a curious fraction, as an inexperienced mathematician in attempting to simplify it may incorrectly believe that ⁴⁹/₉₈ = ⁴/₈, which is correct, is obtained by cancelling the 9s.
We shall consider fractions like, ³⁰/₅₀ = ³/₅, to be trivial examples.
There are exactly four non-trivial examples of this type of fraction, less than one in value, and containing two digits in the numerator and denominator.
If the product of these four fractions is given in its lowest common terms, find the value of the denominator.

Answer : 100

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 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126

import java.util.Arrays; import java.util.HashSet; import java.util.Scanner; public class Solution { private static char[] insert(char[] array, int count, char target) { char[] in_new = new char[array.length + count]; for(int k = 0; k < count; k++) { in_new[k] = target; } for(int k = count; k < in_new.length; k++) { in_new[k] = array[k - count]; } return in_new; } public static boolean nextPermutation(char[] array) { for(int i = array.length - 1; i > 0; i--) { if(array[i - 1] < array[i]) { int dest = array[i - 1]; int s = i; int e = array.length - 1; int swapIndex = 0; while(true) { if(s == e) { swapIndex = s; break; } int m = (s + e + 1) / 2; if(array[m] <= dest) { e = m - 1; } else { s = m; } } char temp = array[swapIndex]; array[swapIndex] = array[i - 1]; array[i - 1] = temp; Arrays.sort(array, i, array.length); return true; } } return false; } private static char[] NumToCharArray(int x, int digits) { String result = String.valueOf(x); while(result.length() != digits) { result = "0" + result; } return result.toCharArray(); } private static int merge(char[] strFill, char[] mask) { int index = 0; int result = 0; for(char m : mask) { result *= 10; if(m == '.') { result += strFill[index] - '0'; index++; } else { result += Character.getNumericValue(m); } } return result; } public static void main(String[] args) { try(Scanner sc = new Scanner(System.in)) { int N = sc.nextInt(); int K = sc.nextInt(); int keep = N - K; int[] Tens = {1, 10, 100, 1000, 10000}; int sumN = 0; int sumD = 0; HashSet<Integer> used = new HashSet<>(); for(int d = 1; d < Tens[keep]; d++) { for(int n = 1; n < d; n++) { char[] charN = NumToCharArray(n, keep); char[] charD = NumToCharArray(d, keep); for(int i = Tens[K - 1]; i < Tens[K]; i++) { char[] in = NumToCharArray(i, K); boolean isAscending = true; for(int j = 1; j < in.length; j++) { if(in[j - 1] > in[j]) { isAscending = false; break; } } if(isAscending) { in = insert(in, keep, '.'); char[] charInsertN = in.clone(); do { int newN = merge(charN, charInsertN); if(newN >= Tens[N - 1]) { char[] charInsertD = in.clone(); do { int newD = merge(charD, charInsertD); if(newN * d == newD * n) { int id = newN * 10000 + newD; if(!used.contains(id)) { sumN += newN; sumD += newD; used.add(id); } } } while(nextPermutation (charInsertD)); } } while(nextPermutation (charInsertN)); } } } } System.out.println(sumN + " " + sumD); } } }