Number of Ways to Build House of Cards - Problem

You are given an integer n representing the number of playing cards you have. A house of cards meets the following conditions:

A house of cards consists of one or more rows of triangles and horizontal cards
Triangles are created by leaning two cards against each other
One card must be placed horizontally between all adjacent triangles in a row
Any triangle on a row higher than the first must be placed on a horizontal card from the previous row
Each triangle is placed in the leftmost available spot in the row

Return the number of distinct house of cards you can build using all n cards. Two houses of cards are considered distinct if there exists a row where the two houses contain a different number of cards.

Input & Output

Example 1 — Small House

$ Input: n = 2

› Output: 1

💡 Note: With 2 cards, we can only build one triangle (using both cards). This forms a single-row house.

Example 2 — Medium House

$ Input: n = 5

› Output: 1

💡 Note: With 5 cards, we can build 2 triangles in one row (2+1+2 = 5 cards total). This is the only valid configuration.

Example 3 — Multiple Options

$ Input: n = 8

› Output: 2

💡 Note: We can build: (1) 3 triangles in one row using all 8 cards, or (2) 2 triangles in first row (5 cards) + 1 triangle in second row (2 cards) + 1 card between levels.

Constraints

1 ≤ n ≤ 500

Visualization

Tap to expand

Asked in

G Google 15 f Facebook 12

The key insight is that each row with k triangles needs exactly 3k-1 cards, and the next row can have at most k-1 triangles. Best approach uses memoized recursion or bottom-up DP to count valid configurations. Time: O(n²), Space: O(n²)

Common Approaches

✓ Bottom-Up Dynamic Programming

⏱️ Time: O(n²) Space: O(n²)

Use a 1D DP array where dp[i] represents the number of ways to build a house with i cards. For each number of cards, try all possible first rows and add the ways to build the remaining structure.

Recursive with Memoization

⏱️ Time: O(n²) Space: O(n²)

For each remaining number of cards, try placing different numbers of triangles in the current row. Use memoization to avoid recalculating the same subproblems. Each row with k triangles uses 3k-1 cards and can support at most k-1 triangles in the next row.

Bottom-Up Dynamic Programming — Algorithm Steps

Initialize dp[0] = 1 (one way to use 0 cards)
For each card count i, try all possible first row sizes
Add dp[remaining] to dp[i] for valid configurations
Return dp[n]

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

dp[0][*] = 1 (one way to use 0 cards)

Fill Table

For each (cards, maxTriangles), try all possible row sizes

Result

dp[n][n] contains the answer

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>

int min(int a, int b) {
    return a < b ? a : b;
}

int solution(int n) {
    int** dp = (int**)malloc((n + 1) * sizeof(int*));
    for (int i = 0; i <= n; i++) {
        dp[i] = (int*)calloc(n + 1, sizeof(int));
    }
    
    for (int maxTri = 0; maxTri <= n; maxTri++) {
        dp[0][maxTri] = 1;
    }
    
    for (int cards = 1; cards <= n; cards++) {
        for (int maxTri = 1; maxTri <= n; maxTri++) {
            int ways = 0;
            for (int k = 1; k <= min(maxTri, cards); k++) {
                int cardsNeeded = 3 * k - 1;
                if (cardsNeeded <= cards) {
                    ways += dp[cards - cardsNeeded][k - 1];
                }
            }
            dp[cards][maxTri] = ways;
        }
    }
    
    int result = dp[n][n];
    
    for (int i = 0; i <= n; i++) {
        free(dp[i]);
    }
    free(dp);
    
    return result;
}

int main() {
    int n;
    scanf("%d", &n);
    int result = solution(n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of n cards, we try O(√n) possible triangle counts for first row

⚠ Quadratic Growth

Space Complexity

O(n²)

2D DP table to track (cards, maxTriangles) states

⚠ Quadratic Space

8.5K Views

Medium Frequency

~35 min Avg. Time

342 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Number of Ways to Build House of Cards - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Bottom-Up Dynamic Programming — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler