Problem Statement
A house of cards is a pyramid-shaped construction made entirely of cards.
The main unit (which we will call a block) consists of two cards leaning against each other, roughly like this:
/\
/ \
The bottom floor of the pyramid consists of N blocks standing next to each other.
As long as you have more than one block, you can build an additional floor. The new floor is built as follows:
- Add a ceiling: For each pair of adjacent blocks on the current top floor, place a horizontal card that will cover both their tops.
- Add the new floor: For each horizontal card you just placed, put a new block onto that card.
Clearly, the new floor will have one fewer block than the previous one.
The pyramid is complete once you build a floor that consists of a single block.
Given the number N of blocks that form the bottom floor, compute and return the total number of cards needed to build the pyramid.
Definition
- Class:
- HouseOfCards
- Method:
- count
- Parameters:
- int
- Returns:
- long
- Method signature:
- long count(int N)
- (be sure your method is public)
Notes
- Watch out for integer overflow: the result may not fit into a 32-bit variable.
Constraints
- N will be between 1 and 100,000, inclusive.
Examples
1
Returns: 2
You take two cards, build a single block, and that's it.
2
Returns: 7
You need four cards to build two blocks, then one card to put on their tops horizontally, and then two more cards to build one block on top of that card. The resulting house of cards looks roughly as follows: /\ / \ ------ /\ /\ / \/ \
4
Returns: 26
We start by placing four blocks next to each other to form the bottom floor. Then we place three cards horizontally on top of them and we are ready to build the next floor. And so on, until the top. An ASCII art of the full house follows. ('=' denotes places where two adjacent horizontal cards partially overlap.) /\ / \ ------ /\ /\ / \/ \ ----==---- /\ /\ /\ / \/ \/ \ ----==--==---- /\ /\ /\ /\ / \/ \/ \/ \
3
Returns: 15
7
Returns: 77
23
Returns: 805
324
Returns: 157626
6543
Returns: 64219545
100000
Returns: 15000050000
99997
Returns: 14999150012
98578
Returns: 14576482415
89990
Returns: 12147345145
86745
Returns: 11287085910
46784
Returns: 3283137376