How to increase the speed of calculation the number of specific leaves in tree

Question

I have the programming assignment I can't solve withing the given constraints.

Conditions:

You have N amount of bricks.

Calculate how many staircases you can build with these bricks with following constraints:

1. Each staircase should be built using all given bricks.
2. Two steps with the same height are not allowed.
3. Staircase should have at least 2 steps.
4. Maximal number of bricks will be provided is 250.

Examples:

Given 3 bricks, you can build 1 staircase:

step 1 - height 1
step 2 - height 2

Given 4 bricks, you also can build 1 staircase:

step 1 - height 1
step 2 - height 3

Given 5 bricks, you can build 2 staircases:

step 1 - height 2            step 1 - height 1
step 2 - height 3            step 2 - height 4

The solution should be implemented like following (I am using Java):

class Solution {
  public static int count(int numberOfBricks) {
    // code
  }
}

The automatic grader has several technical constraints, ex. threads are not allowed, a lot of Java classes are limited and so on.

I tried to solve the problem using tree structures where each node keeps information about the number of the bricks left and current step height, and each edge represents the building of the step with allowed height.

For example, the following structures represents staircases with step heights (1,2,4) (1,6) (2,5) (3,4)

tree structure

I tried several approaches:

1. Building staircase bottom-up (from lowest step to highest) and top-down (from highest step to lowest)
2. Use deep-first and breadth-first search.
3. Using recursion or iteration.

As a result I have several working solutions that pass unit tests (solve all sample problems correctly). Unfortunately I can't receive the highest grade, because automatic grader tells me that my solutions are behind allowed time limits, so some more optimal way exists. I guess the key is to limit traversal along the branches by calculation of the possible number of staircases on the base of the current node. Unfortunately I have not enough knowledge for the following improvements and will appreciate any help. Here is one of my solution:

import org.testng.Assert;

public class Task0302 {

static int numberOfStairCases = 0;

public static int answer(int n) {   
  numberOfStairCases = 0;
  run(n, n - 1);
  return numberOfStairCases;
}

static void run(final int hasBricks, final int maximalAllowedHeight) {
  if (hasBricks > bricksAllowed(maximalAllowedHeight))
    return;
  if (hasBricks == bricksAllowed(maximalAllowedHeight)) {
    numberOfStairCases++;
    return;
}

int currentStepHeight = Math.min(hasBricks, maximalAllowedHeight);
final int minHeight = minPossibleHeight(hasBricks);
 do {    
   run(hasBricks - currentStepHeight, currentStepHeight - 1);
   currentStepHeight--;
 } while (currentStepHeight >= minHeight);
}

static int minPossibleHeight(int havingBricks) {
  return (int) ((Math.sqrt(8 * havingBricks + 1) - 1) / 2);
}

static int bricksAllowed(int currentHeight) {
  return (currentHeight + 1) * currentHeight / 2;
}

public static void main(String[] args) {
 Assert.assertEquals(answer(3), 1);
 Assert.assertEquals(answer(4), 1);
 Assert.assertEquals(answer(5), 2);
 Assert.assertEquals(answer(200), 487067745);
 System.out.println("Passed");
 }
}

Sorry, it is messy because I am studying mostly during nights and work all day. The python 2 also can be used, but I am not professional in it.

Answer 1

You question is equivalent to counting the number of ways of summing to N with unique positive integers, ignoring order. There's a reference here: http://mathworld.wolfram.com/PartitionFunctionQ.html

One O(n^2) algorithm using the generating function in the above link is to compute the polynomial product: product((1+x^k) for k = 1..N), and then look at the coefficient of x^N.

That sounds difficult, but the code for it is relatively simple (here in pseudocode):

A = [1, 0, 0, ..., 0] -- an array of size N+1
for k = 1 to N
    for i = N to k step -1
        A[i] += A[i - k]
return A[N]

You can think of this as a dynamic programming solution. After n steps of the k loop, each A[i] will store the number of different ways of summing to i using the integers 1 to n. Or equivalently, after n steps of the k loop, you can consider the array A to represent the polynomial A[0] + A[1]x + A[2]x^2 + ... + A[N]x^N, which will be equal to product(1+x^k for k=1..n).

(Actually, this solution includes the "stair" with one step of size N -- so you'll have to subtract 1 to get the result excluding this special case).