Douglas Leite
BAN USERpublic static boolean reachTheEnd(int[] a) {
return reachTheEnd(a, 0);
}
private static boolean reachTheEnd(int[] a, int i) {
if (i == a.length - 1) return true;
else if (i > a.length - 1) return false;
int hops = a[i];
while (hops > 0) {
if (reachTheEnd(a, i + hops--)) return true;
}
return false;
}
public static String pattern(final int input) {
if (input == 0) return "1";
final String ans = pattern(input - 1);
final StringBuilder resultStr = new StringBuilder();
int count = 0;
char curr = 0;
for (final char c : ans.toCharArray()) {
if (count == 0) {
curr = c;
count = 1;
} else if (curr == c) {
count++;
} else {
resultStr.append(String.valueOf(count))
.append(String.valueOf(curr));
curr = c;
count = 1;
}
}
resultStr.append(String.valueOf(count))
.append(String.valueOf(curr));
return resultStr.toString();
}
Try inserting this line of code before `count++`:
System.out.println(String.format("%d = %d ^2 + %d ^2", n, (int) x, y));
Then, using 25 as input, you should get this:
25 = 5 ^2 + 0 ^2
25 = 4 ^2 + 3 ^2
The number of combinations for 25 is: 2
Here is my code in Java that uses a binary search to solve the problem. This implementation of binary search is aware of duplicates, and returns the first position where the element being searched occurs in the array.
In case of more than one row in the matrix contains the same number of 1's, the latest row will be returned. This can be easily fixed maintaining a data structure to store all indexes with the same result of binary search.
- Douglas Leite January 27, 2015