We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Number of Ways to Build House of Cards

Number: 1385

Difficulty: Medium

Paid? Yes

Companies: Airbnb

Problem Description

Given n playing cards, count the number of distinct ways to build a valid house of cards that satisfies these conditions:

  • A house of cards consists of one or more rows.
  • Each row is made up of “triangles” (each triangle uses 2 cards) and horizontal cards placed between adjacent triangles.
  • In a row with k triangles, the cards used = 2k (for the triangles) plus (k-1) horizontal cards (one between each adjacent pair), for a total of (3k - 1) cards.
  • For every row after the first, each triangle must be built on a horizontal card from the row below. Thus, if a row has r triangles, the row above it can have at most (r - 1) triangles.
  • Two houses of cards are distinct if there is a row for which they use a different number of cards. The goal is to use all n cards exactly and count how many distinct configurations are possible.

Key Insights

  • Each row with r triangles requires (3*r - 1) cards.
  • The first row can have any number of triangles, say r₁, as long as (3*r₁ - 1) ≤ n.
  • For every subsequent row, if the row below has r triangles, the next row can have any number between 1 and (r - 1).
  • The problem reduces to partitioning n cards into segments, where each segment (row) has a cost (3*r - 1) and the allowed number of triangles in each row is constrained by the row below.
  • A recursion (or dynamic programming) with state (remaining cards, maximum allowed triangles for the next row) is a natural approach.

Space and Time Complexity

Time Complexity: O(n × m) where m is roughly O(n/3), since for each remaining card count we iterate over possible triangle counts. Space Complexity: O(n × m) for the memoization table.

Solution

We can solve the problem using top-down dynamic programming with memoization. Define a function f(rem, cap) which counts the ways to use exactly rem cards in rows, where the next row is allowed at most “cap” triangles. For the first row, cap is determined by the maximum triangles possible given n (computed from the inequality 3r - 1 ≤ n). For each possible r from 1 to cap, if (3r - 1) ≤ rem, we subtract its cost and recursively count the ways for the remainder with an updated cap of (r - 1). The recursion stops when rem equals 0 (a valid configuration is completed). Otherwise, if no valid r can be chosen, that branch yields 0. This approach efficiently explores the valid “stacks” that satisfy the constraint.

Code Solutions

# Python solution for counting ways to build the house of cards.
def numWays(n: int) -> int:
    # Import lru_cache for memoization
    from functools import lru_cache
    
    # Maximum triangles for first row derived from the inequality: 3*r - 1 <= n
    max_triangles = (n + 1) // 3

    @lru_cache(maxsize=None)
    def dp(rem: int, cap: int) -> int:
        # If no cards remain, we have formed a valid configuration.
        if rem == 0:
            return 1
        ways = 0
        # Try every possible number of triangles for the current row from 1 to cap.
        for r in range(1, cap + 1):
            cost = 3 * r - 1  # Cards needed for a row with r triangles
            if cost > rem:
                break  # Further r will only increase cost
            # Move to next row with a new cap = r - 1
            ways += dp(rem - cost, r - 1)
        return ways

    return dp(n, max_triangles)

# Example usage:
if __name__ == "__main__":
    n = 16
    print(numWays(n))  # Expected output: 2
← Back to All Questions