Code Sample – WalPrimes

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