Google foobar challenge

Seawolf

Level 3

The Grandest Staircase Of Them All

With her LAMBCHOP doomsday device finished, Commander Lambda is preparing for her debut on the galactic stage - but in order to make a grand entrance, she needs a grand staircase! As her personal assistant, you've been tasked with figuring out how to build the best staircase EVER.

Lambda has given you an overview of the types of bricks available, plus a budget. You can buy different amounts of the different types of bricks (for example, 3 little pink bricks, or 5 blue lace bricks). Commander Lambda wants to know how many different types of staircases can be built with each amount of bricks, so she can pick the one with the most options.

Each type of staircase should consist of 2 or more steps. No two steps are allowed to be at the same height - each step must be lower than the previous one. All steps must contain at least one brick. A step's height is classified as the total amount of bricks that make up that step. For example, when N = 3, you have only 1 choice of how to build the staircase, with the first step having a height of 2 and the second step having a height of 1: (# indicates a brick)

1. #
   
2. ##
   
3. 21

复制代码

When N = 4, you still only have 1 staircase choice:

1. #
   
2. #
   
3. ##
   
4. 31

复制代码

But when N = 5, there are two ways you can build a staircase from the given bricks. The two staircases can have heights (4, 1) or (3, 2), as shown below:

1. #
   
2. #
   
3. #
   
4. ##
   
5. 41
   
6. 
   
7. #
   
8. ##
   
9. ##
   
10. 32

复制代码

Write a function called answer(n) that takes a positive integer n and returns the number of different staircases that can be built from exactly n bricks. n will always be at least 3 (so you can have a staircase at all), but no more than 200, because Commander Lambda's not made of money!

Inputs:

(int) n = 3
Output:

(int) 1
Inputs:

(int) n = 200
Output:

(int) 487067745

1. //using divide and conquer
   
2. //divide a number into two numbers for example 7- 16,25,34
   
3. //the look at the last digit to see if it is can be divide into two numbers  6 - 24
   
4. //and do it recursively, this method is not optimal, I am sure we can find a better one together
   
5. 
   
6. package com.company;
   
7. 
   
8. import java.util.ArrayList;
   
9. 
   
10. public class Main {
    
11. 
    
12.     // the container to store those solutions
    
13.     private static ArrayList<String> memo = new ArrayList<String>();
    
14. 
    
15.     // every single possible solution and it will be overwritten after each solution is finished
    
16.     private static String result = "";
    
17. 
    
18.     //total number of the solution
    
19.     private static int count = 0;
    
20. 
    
21.     private static int init = 0;
    
22. 
    
23. 
    
24.     public static void main(String[] args) {
    
25. 
    
26.         // test number
    
27.         int n = 10;
    
28. 
    
29.         solution1(n);
    
30.         solution1(n);
    
31.         
    
32. 
    
33.         //print all the solutions and the number of solutions
    
34.         print_list(memo);
    
35.         System.out.println(count);
    
36. 
    
37. //        return count;a
    
38. 
    
39.     }
    
40. 
    
41. 
    
42.     //contruct the first time situation
    
43.     private static void solution1(int n) {
    
44. 
    
45.         if (init == 0) {
    
46. 
    
47.             for (int i = 1; i < n - 1; i++) {
    
48. 
    
49.                 if (i < n - i) {
    
50. 
    
51.                     int re = n - i;
    
52. 
    
53.                     result = result + i;
    
54. 
    
55.                     result = result + ",";
    
56. 
    
57.                     result = result + re;
    
58. 
    
59.                     result = result + ",";
    
60. 
    
61. 
    
62. 
    
63.                     if(!memo.contains(result)){
    
64. 
    
65.                         count++;
    
66. 
    
67.                         memo.add(result);
    
68. 
    
69. 
    
70.                     }
    
71. 
    
72.                     result = "";
    
73. 
    
74.                 }
    
75. 
    
76. 
    
77. 
    
78.             }
    
79. 
    
80. //            print_list(memo);
    
81.             init ++;
    
82.         }else{
    
83. 
    
84. 
    
85. 
    
86.             for(int i = 0; i < memo.size(); i ++){
    
87. 
    
88.                 // the string array to store each digit, adding a coma is because consider the 11 case
    
89.                 // there is possible to be 1 and 10, for a string it cannot tell if it is one digit number or two
    
90.                 String[] test = memo.get(i).substring(0,memo.get(i).length()-1).split(",");
    
91. 
    
92. //            for (String a: test) {
    
93. //
    
94. //                System.out.print(a);
    
95. //
    
96. //            }
    
97. //
    
98. //            System.out.println();
    
99. 
    
100.                 //get last digit
     
101.                 String last =  test[test.length-1];
     
102. 
     
103.                 //get last second digit
     
104.                 String lastsec = test[test.length-2];
     
105. 
     
106.                 //get former digit beside the last one
     
107.                 String former = "";
     
108. 
     
109.                 //construct the former digit
     
110.                 for(int x = 0 ; x <test.length -1; x++){
     
111. 
     
112.                     if(x != 0){
     
113. 
     
114.                         former =former + ",";
     
115. 
     
116.                     }
     
117. 
     
118. 
     
119.                     former =former + test[x];
     
120. 
     
121.                 }
     
122. 
     
123. //            System.out.println(last);
     
124. //
     
125. //            System.out.println(lastsec);
     
126. //
     
127. //            System.out.println("----"+ former);
     
128. 
     
129.                 //convert last digit string to an integer
     
130.                 int lst = Integer.parseInt(last);
     
131. 
     
132. 
     
133.                 //convert last second digit string to an integer
     
134.                 int lstsec = Integer.parseInt(lastsec);
     
135. 
     
136. 
     
137.                 //construct each possible solution for more than one time situation
     
138.                 if( lst >= 2* lstsec+ 3){
     
139. 
     
140.                     for (int j = 1; j < lst - 1; j++) {
     
141. 
     
142.                         if (j < lst - j && j >lstsec) {
     
143. 
     
144.                             int re = lst - j;
     
145. 
     
146.                             result = result + former;
     
147. 
     
148.                             result = result +  ",";
     
149. 
     
150.                             result = result + j;
     
151. 
     
152.                             result = result +  ",";
     
153. 
     
154.                             result = result + re;
     
155. 
     
156.                             result = result +  ",";
     
157. 
     
158. 
     
159.                             if(!memo.contains(result)){
     
160. 
     
161.                                 count ++;
     
162. 
     
163.                                 memo.add(result);
     
164. 
     
165. //                                System.out.println(result);
     
166. 
     
167.                             }
     
168. 
     
169. 
     
170.                             result = "";
     
171. 
     
172.                         }
     
173.                     }
     
174. 
     
175.                 }
     
176. 
     
177.             }
     
178. 
     
179.         }
     
180. 
     
181.     }
     
182. 
     
183.     //print the list
     
184.     private static void print_list(ArrayList memo){
     
185. 
     
186.         for(int i = 0 ; i<memo.size();i++){
     
187. 
     
188.             System.out.println(memo.get(i).toString().replaceAll(",",""));
     
189. 
     
190.         }
     
191.     }
     
192. 
     
193. 
     
194. 
     
195. }
     

复制代码

这个code可以算出所有的case，但是当n足够大的时候，系统会run out of memory，所以有一下solution：

1. import java.lang.Math;
   
2. 
   
3. public class PartitionCounter
   
4. {
   
5.   public static void main(String[] args)
   
6. 
   
7.   {
   
8. 
   
9.     int F[] = new int[201];
   
10. 
    
11.     F[0]=1;
    
12. 
    
13.     F[1]=1;
    
14. 
    
15.     for(int n=2; n<201; n++){
    
16. 
    
17. 
    
18.       for(int k=200; k>n-1; k--){
    
19. 
    
20.         F[k] = F[k]+F[k-n];
    
21. 
    
22.       }
    
23. 
    
24.     }
    
25. 
    
26.     System.out.print("[");
    
27.     for(int k=0; k<200; k++){
    
28.         System.out.print((F[k]-1) + ", ");
    
29.     }
    
30.     System.out.print("]");
    
31.   }
    
32. }

复制代码