Category Archives: CodingBat: Java

CodingBat: Java. Recursion-1, Part III

countPairs:

public int countPairs(String str) {
	if (str.length() < 3) return 0;
	if (str.charAt(0) == str.charAt(2))
		return 1 + countPairs(str.substring(1));
	return countPairs(str.substring(1));
}

countAbc:

public int countAbc(String str) {
	if (str.length() < 3) return 0;
	if (str.substring(0, 3).equals("abc") 
			|| str.substring(0, 3).equals("aba"))
		return 1 + countAbc(str.substring(1));
	return countAbc(str.substring(1));
}

count11:

public int count11(String str) {
	if (str.length() < 2) return 0;
	if (str.substring(0, 2).equals("11"))
		return 1 + count11(str.substring(2));
	return count11(str.substring(1));
}

stringClean:

public String stringClean(String str) {
	if (str.length() < 2) return str;
	if (str.charAt(0) == str.charAt(1))
		return stringClean(str.substring(1));
	return str.charAt(0) + stringClean(str.substring(1));
}

countHi2:

public int countHi2(String str) {
	if (str.length() < 2) return 0;
	if (str.substring(0, 2).equals("hi"))
		return 1 + countHi2(str.substring(2));
	if (str.charAt(0) == 'x' && str.length() >= 3) {
		if (str.substring(1, 3).equals("hi"))
			return countHi2(str.substring(3));
		return countHi2(str.substring(1));
	}
	return countHi2(str.substring(1));
}

parenBit:

public String parenBit(String str) {
	if (!str.substring(0, 1).equals("("))
		return parenBit(str.substring(1));
	return (str.substring(0, str.indexOf(")") + 1));
}

nestParen:

public boolean nestParen(String str) {
	if (str.equals("") || str.equals("()")) return true;
	if (str.charAt(0) == '(' && str.charAt(str.length() - 1) == ')')
		return nestParen(str.substring(1, str.length() - 1));
	return false;
}

strCount:

public int strCount(String str, String sub) {
	if (str.length() < sub.length()) return 0;
	if (str.substring(0, sub.length()).equals(sub))
		return 1 + strCount(str.substring(sub.length()), sub);
	return strCount(str.substring(1), sub);
}

strCopies:

public boolean strCopies(String str, String sub, int n) {
	if (str.length() < sub.length()) return (n <= 0);
	if (str.substring(0, sub.length()).equals(sub))
		return strCopies(str.substring(1), sub, n - 1);
	return strCopies(str.substring(1), sub, n);
}

strDist:

public int strDist(String str, String sub) {
	if (str.indexOf(sub) == -1) return 0;
	if (str.substring(0, sub.length()).equals(sub)
			&& str.substring(str.length() - sub.length())
			.equals(sub))
		return str.length();
	if (!str.substring(0, sub.length()).equals(sub))
		return strDist(str.substring(1), sub);
	// case: (!str.substring(str.length()-sub.length()).equals(sub))
	return strDist(str.substring(0, str.length() - 1), sub);
}

CodingBat: Java. Recursion-1, Part II

countHi:

public int countHi(String str) {
	if (str.length() < 2) return 0;
	if (str.substring(0, 2).equals("hi"))
		return 1 + countHi(str.substring(2));
	return countHi(str.substring(1));
}

changeXY:

public String changeXY(String str) {
	if (str.length() == 0) return str;
	if (str.charAt(0) == 'x') return "y" + changeXY(str.substring(1));
	return str.charAt(0) + changeXY(str.substring(1));
}

changePi:

public String changePi(String str) {
	if (str.length() < 2) return str;
	if (str.substring(0, 2).equals("pi"))
		return "3.14" + changePi(str.substring(2));
	return str.charAt(0) + changePi(str.substring(1));
}

noX:

public String noX(String str) {
	if (str.length() == 0) return "";
	if (str.charAt(0) == 'x') return noX(str.substring(1));
	return str.charAt(0) + noX(str.substring(1));
}

array6:

public boolean array6(int[] nums, int index) {
	if (nums.length == 0) return false;
	if (index == nums.length - 1) return nums[index] == 6;
	if (nums[index] == 6) return true;
	return array6(nums, index + 1);
}

array11:

public int array11(int[] nums, int index) {
	if (index == nums.length) return 0;
	if (nums[index] == 11) return 1 + array11(nums, index + 1);
	return array11(nums, index + 1);
}

array220:

public boolean array220(int[] nums, int index) {
	if (nums.length < 2 || index == nums.length - 1) return false;
	if (nums[index + 1] == nums[index] * 10) return true;
	return array220(nums, index + 1);
}

allStar:

public String allStar(String str) {
	if (str.length() <= 1) return str;
	return str.charAt(0) + "*" + allStar(str.substring(1));
}

pairStar:

public String pairStar(String str) {
	if (str.length() < 2) return str;
	if (str.charAt(0) == str.charAt(1))
		return str.charAt(0) + "*" + pairStar(str.substring(1));
	return str.charAt(0) + pairStar(str.substring(1));
}

endX:

public String endX(String str) {
	if (str.length() == 0) return str;
	if (str.charAt(0) == 'x')
		return endX(str.substring(1)) + "x";
	return str.charAt(0) + endX(str.substring(1));
}

CodingBat: Java. Recursion-1, Part I

Recursion is neat in theory and commonly leads to very clean code. Some people have a hard time understanding it, though. If you’ve ever encountered a recurrence relation in mathematics, then you already know everything there is to know about the “mind-bending” nature of recursive problems.

Otherwise, try this simple strategy. First, you may be tempted to think recursively about recursive functions. This may work with factorials, but for something more complex like, say, the Ackermann function, it’s a recipe for disaster. So, don’t do it! Instead, figure out what the base case consists of. The base case immediately returns a result. All other conditions eventually have to revert to the base case, which means that you’ll return “something” in addition to recursively calling the function, but with an input that brings you closer to the base case.

The first example, factorial, of CodingBat’s Recursion-1 section illustrates this strategy very well. All subsequent problems are rather similar.

All solutions were successfully tested on 24 March 2013.

factorial:

public int factorial(int n) {
	if (n <= 1) return 1;
	return n * factorial(n - 1);
}

bunnyEars:

public int bunnyEars(int bunnies) {
	if (bunnies == 0) return 0;
	return 2 + bunnyEars(bunnies - 1);
}

fibonacci:

public int fibonacci(int n) {
	if (n <= 1) return n;
	return fibonacci(n - 2) + fibonacci(n - 1);
}

bunnyEars2:

public int bunnyEars2(int bunnies) {
	if (bunnies == 0) return 0;
	if (bunnies % 2 == 1) return 2 + bunnyEars2(bunnies - 1);
	return 3 + bunnyEars2(bunnies - 1);
}

triangle:

public int triangle(int rows) {
	if (rows == 0) return 0;
	return rows + triangle(rows - 1);
}

sumDigits:

public int sumDigits(int n) {
	if (n == 0) return 0;
	return n % 10 + sumDigits(n / 10);
}

count7:

public int count7(int n) {
	if (n == 0) return 0;
	if (n % 10 == 7) return 1 + count7(n / 10);
	return count7(n / 10);
}

count8:

public int count8(int n) {
	if (n == 0) return 0;
	if (n >= 88 && n % 100 == 88) return 2 + count8(n / 10);
	if (n % 10 == 8) return 1 + count8(n / 10);
	return count8(n / 10);
}

powerN:

public int powerN(int base, int n) {
	if (n == 0) return 1;
	return base * powerN(base, n - 1);
}

countX:

public int countX(String str) {
	if (str.length() == 0) return 0;
	if (str.charAt(0) == 'x') return 1 + countX(str.substring(1));
	return countX(str.substring(1));
}

CodingBat: Java. AP-1, Part III

scoresSpecial:

public int scoresSpecial(int[] a, int[] b) {
	return largest(a) + largest(b);
}


public int largest(int[] array) {
	int result = 0;
	for (int i = 0; i < array.length; i++)
		if (array[i] % 10 == 0 && array[i] > result)
			result = array[i];
	return result;
}

sumHeights:

public int sumHeights(int[] heights, int start, int end) {
	int sum = 0;
	for (int i = start; i < end; i++)
		sum += Math.abs(heights[i] - heights[i + 1]);
	return sum;
}

sumHeights2:

public int sumHeights2(int[] heights, int start, int end) {
	int sum = 0;
	for (int i = start; i < end; i++)
		if (heights[i] < heights[i + 1])
			sum += (2 * Math.abs(heights[i] - heights[i + 1]));
		else
			sum += Math.abs(heights[i] - heights[i + 1]);
	return sum;
}

bigHeights:

public int bigHeights(int[] heights, int start, int end) {
	int count = 0;
	for (int i = start; i < end; i++)
		if (Math.abs(heights[i] - heights[i + 1]) >= 5) count++;
	return count;
}

userCompare:

public int userCompare(String aName, int aId, String bName, int bId) {
	if (aName.compareTo(bName) < 0) return -1;
	if (aName.equals(bName)) {
		if (aId == bId) return 0;
		if (aId < bId) return -1;
	}
	return 1;
}

mergeTwo:

public String[] mergeTwo(String[] a, String[] b, int n) {
	String[] result = new String[n];
	int indexResult = 0;
	int indexA = 0;
	int indexB = 0;

	while (indexResult < n)
		if (a[indexA].compareTo(b[indexB]) < 0)
			result[indexResult++] = a[indexA++];
		else if (a[indexA].compareTo(b[indexB]) > 0)
			result[indexResult++] = b[indexB++];
		else { // identical strings
			result[indexResult++] = a[indexA++];
			indexB++;
		}
	return result;
}

commonTwo:

public int commonTwo(String[] a, String[] b) {
	int count = 0;
	String lastChecked = null;
	for (int i = 0; i < a.length; i++)
		if (!a[i].equals(lastChecked))
			for (int j = 0; j < b.length; j++)
				if (a[i].equals(b[j])) {
					count++;
					lastChecked = a[i];
					break;
				}
	return count;
}

CodingBat: Java. AP-1, Part II

hasOne:

public boolean hasOne(int n) {
	while (n > 0) {
		if (n % 10 == 1) return true;
		n = n / 10;
	}
	return false;
}

dividesSelf:

public boolean dividesSelf(int n) {
	int copyN = n;
	while (n > 0)
		if (n % 10 == 0) return false;
		else
			if (copyN % (n % 10) == 0) n /= 10;
			else return false;
	return true;
}

copyEvens:

public int[] copyEvens(int[] nums, int count) {
	int[] result = new int[count];
	int position = 0;

	for (int i = 0; i < nums.length; i++) {
		if (nums[i] % 2 == 0) {
			result[position] = nums[i];
			position++;
		}
		if (position == count) break;
	}
	return result;
}

copyEndy:

public int[] copyEndy(int[] nums, int count) {
	int[] result = new int[count];
	for (int i = 0, pos = 0; i < nums.length; i++) {
		if (nums[i] >= 0 && nums[i] <= 10 || nums[i] >= 90
				&& nums[i] <= 100) {
			result[pos] = nums[i];
			pos++;
		}
		if (pos == count) break;
	}
	return result;
}

matchUp:

public int matchUp(String[] a, String[] b) {
	int count = 0;
	for (int i = 0; i < a.length; i++)
		if (!a[i].equals("") && !b[i].equals("")
				&& a[i].charAt(0) == b[i].charAt(0))
			count++;
	return count;
}

scoreUp:

public int scoreUp(String[] key, String[] answers) {
	int sum = 0;
	for (int i = 0; i < answers.length; i++)
		if (answers[i] == key[i]) sum += 4;
		else if (!answers[i].equals("?")) sum -= 1;
	return sum;
}

wordsWithout:

public String[] wordsWithout(String[] words, String target) {
	int count = 0;
	for (int i = 0; i < words.length; i++)
		if (!words[i].equals(target)) count++;

	String[] result = new String[count];
	for (int i = 0, pos = 0; i < words.length; i++)
		if (!words[i].equals(target)) {
			result[pos] = words[i];
			pos++;
		}
	return result;
}