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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s