Project Euler > Problem 114 > Counting block combinations I (Java Solution)


A row measuring seven units in length has red blocks with a minimum length of three units placed on it, such that any two red blocks (which are allowed to be different lengths) are separated by at least one black square. There are exactly seventeen ways of doing this.

How many ways can a row measuring fifty units in length be filled?

NOTE: Although the example above does not lend itself to the possibility, in general it is permitted to mix block sizes. For example, on a row measuring eight units in length you could use red (3), black (1), and red (4).



The solution may include methods that will be found here: .

public interface EulerSolution{

public String run();

* Solution to Project Euler problem 14
* By Nayuki Minase

import java.math.BigInteger;

public final class p014 implements EulerSolution {

public static void main(String[] args) {
System.out.println(new p014().run());

private static final int LIMIT = Library.pow(10, 6);
private static final BigInteger CACHE_SIZE = BigInteger.valueOf(LIMIT); // Any non-negative number, though there are diminishing returns

public String run() {
int maxArg = -1;
int maxChain = 0;
for (int i = 1; i < LIMIT; i++) {
int chainLen = collatzChainLength(BigInteger.valueOf(i));
if (chainLen > maxChain) {
maxArg = i;
maxChain = chainLen;
return Integer.toString(maxArg);

// Memoization
private int[] collatzChainLength = new int[CACHE_SIZE.intValue()];

private int collatzChainLength(BigInteger n) {
if (n.signum() < 0)
throw new IllegalArgumentException();

if (n.compareTo(CACHE_SIZE) >= 0) // Caching not available
return collatzChainLengthDirect(n);

int index = n.intValue(); // Index in the cache
if (collatzChainLength[index] == 0)
collatzChainLength[index] = collatzChainLengthDirect(n);
return collatzChainLength[index];

private int collatzChainLengthDirect(BigInteger n) {
if (n.equals(BigInteger.ONE)) // Base case
return 1;
else if (!n.testBit(0)) // If n is even
return collatzChainLength(n.shiftRight(1)) + 1;
else // Else n is odd
return collatzChainLength(n.multiply(BigInteger.valueOf(3)).add(BigInteger.ONE)) + 1;


No comments :

Post a Comment

Follow Me

If you like our content, feel free to follow me to stay updated.


Enter your email address:

We hate spam as much as you do.

Upload Material

Got an exam, project, tutorial video, exercise, solutions, unsolved problem, question, solution manual? We are open to any coding material. Why not upload?


Copyright © 2012 - 2014 Java Problems  --  About  --  Attribution  --  Privacy Policy  --  Terms of Use  --  Contact