Number of Ways to Build House of Cards - Practice Coding Problems

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

Understanding the Visualization

Input

n = 8 playing cards to use

Build Rules

Triangles need 2 cards, horizontal cards separate triangles, upper rows supported by lower

Count Ways

Find all distinct valid house configurations

Key Takeaway

🎯 Key Insight: Each configuration is defined by triangle counts per row, with structural constraints limiting possibilities

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

Approach	Time	Space	Notes
✓ Recursive with Memoization	O(n²)	O(n²)	Try all possible row configurations recursively
Bottom-Up Dynamic Programming	O(n²)	O(n²)	Build solution iteratively from smaller card counts

Recursive with Memoization — Algorithm Steps

Calculate cards needed for k triangles: 3k-1
Try all valid triangle counts for current row
Recursively solve for remaining cards
Use memoization to cache results

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Begin with n cards, unlimited triangles for first row

Try Rows

For each row, try 1 to k triangles (3k-1 cards each)

Recurse

Solve subproblem with remaining cards, max k-1 triangles

Code -

solution.c — C

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

#define MAX_MEMO 10000
typedef struct {
    int cards;
    int maxTriangles;
    int result;
    int used;
} MemoEntry;

MemoEntry memo[MAX_MEMO];
int memoSize = 0;

int findMemo(int cards, int maxTriangles) {
    for (int i = 0; i < memoSize; i++) {
        if (memo[i].used && memo[i].cards == cards && memo[i].maxTriangles == maxTriangles) {
            return memo[i].result;
        }
    }
    return -1;
}

void addMemo(int cards, int maxTriangles, int result) {
    if (memoSize < MAX_MEMO) {
        memo[memoSize].cards = cards;
        memo[memoSize].maxTriangles = maxTriangles;
        memo[memoSize].result = result;
        memo[memoSize].used = 1;
        memoSize++;
    }
}

int dp(int cards, int maxTriangles) {
    if (cards == 0) return 1;
    if (cards < 0) return 0;
    
    int cached = findMemo(cards, maxTriangles);
    if (cached != -1) return cached;
    
    int ways = 0;
    for (int k = 1; k <= maxTriangles; k++) {
        int cardsNeeded = 3 * k - 1;
        if (cardsNeeded <= cards) {
            ways += dp(cards - cardsNeeded, k - 1);
        }
    }
    
    addMemo(cards, maxTriangles, ways);
    return ways;
}

int solution(int n) {
    memoSize = 0;
    return dp(n, n);
}

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 O(n) cards remaining, we try O(√n) possible triangle counts

⚠ Quadratic Growth

Space Complexity

O(n²)

Memoization table stores results for each (cards, maxTriangles) pair

⚠ 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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Recursive with Memoization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler