The problem defined in here. There are solution codes also. The difference between this code and all the others is, there is **no recursion**, we are just **counting**. Since recursion will **consume all your heap** eventually on a long string, you won’t be able to see the end of the movie.

Note: int overflow containing operations are 0 and they are added to the walnum.

public class WalPrimes { public static void main(String[] args) { System.out.println(walNum("011")); System.out.println(walNum("1256700912856789")); } public static Integer walNum(String s) { int[] perms = new int[s.length() - 1]; initialize(perms); int total = 0; while (perms != null) { total += checkWall(s, perms); perms = getNextPerm(perms); } return total; } public static void initialize(int[] perms) { for (int i = 0; i < perms.length; i++) perms[i] = 0; } public static int checkWall(String s, int[] perms) { int total = 0; int multiplier = 1; int series = 0; // no sign for first element;skip it // least significant digit is at the end // start from end for (int i = perms.length - 1; i >= 0; i--) { if (perms[i] == 0) { series += multiplier * (s.charAt(i+1) - 'a'); multiplier *= 10; } else { series += multiplier * (s.charAt(i+1) - 'a'); multiplier = 1; total += series * (perms[i] == 1 ? 1 : -1); series = 0; } } //take the first digit series += multiplier * (s.charAt(0) - 'a'); total += series; if (total % 2 == 0 || total % 3 == 0 || total % 5 == 0 || total % 7 == 0) return 1; return 0; } public static int[] getNextPerm(int[] perms) { //3 options to branch //counting on base 3 int carry = 1; for (int i = 0; i < perms.length; i++) { if (perms[i] + carry == 3) { if(i == perms.length - 1) return null; perms[i] = 0; } else { perms[i] += carry; return perms; } } return null; } }

Advertisements