Problem

Given an integer N, determine how many distinct Max Heaps can be made from N distinct integers (e.g., 1 to N).

A Max Heap is a complete binary tree where every node is greater than all its children. The structure of the heap is always a complete binary tree, and only the arrangement of values changes.

Input:

  • Integer N (number of distinct elements)

Output:

  • Integer: Number of distinct Max Heaps that can be formed from N distinct elements. (Return answer modulo 1e9+7 if required)

Examples

Example 1

1
2
3
4
5
6
7
8
9

Input: n = 3
Output: 2
Explanation:
The two possible max heaps for N=3 are:


  3      3
 / \    / \
1   2  2   1

Example 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

Input: n = 4
Output: 3
Explanation:
The three possible max heaps for N=4 are:


      4         4         4
     / \       / \       / \
    3   2     2   3     3   1
  /         /         /
 1         1         2

Example 3

1
2
3
4

Input: n = 1
Output: 1
Explanation:
Only one heap possible.

Example 4

1
2
3
4

Input: n = 0
Output: 1
Explanation:
Empty heap is a valid heap.

Constraints

  • N <= 100

Solution

Method 1: DP + Combinatorics

Intuition

A Max Heap is a special kind of complete binary tree where every parent node is greater than its children, and the tree is as compact as possible (all levels are filled except possibly the last, which is filled from left to right). For any set of N distinct integers, the largest value must always be at the root of the heap. The remaining (N-1) elements must be distributed among the left and right subtrees, which themselves must also be max heaps and must together form a complete binary tree structure.

The key insight is that the structure of the heap (i.e., the number of nodes in the left and right subtrees) is completely determined by N, due to the properties of complete binary trees. Once the root is fixed, the number of ways to form the heap is determined by:

  1. Choosing which elements go to the left subtree (the rest go to the right subtree).
  2. Recursively arranging those elements into valid max heaps in the left and right subtrees.

Thus, the total number of max heaps for N elements is:

C(N-1, L) × ways(L) × ways(R)

where L is the number of nodes in the left subtree, R = N-1-L, and ways(k) is the number of max heaps for k elements.

The challenge is to efficiently compute L for any N, and to avoid recomputation by using dynamic programming and precomputed binomial coefficients.

Approach

  1. Base Case: If N is 0 or 1, there is only one possible heap (empty or single node).

  2. Root Placement: The largest element always goes at the root.

  3. Heap Structure: For a given N, the structure of the complete binary tree determines exactly how many nodes go to the left and right subtrees. This is computed by:

    • Finding the height h of the heap: h = floor(log2(N)).
    • The maximum number of nodes at the last level: m = 2^h.
    • The number of nodes actually present at the last level: p = N - (2^h - 1).
    • If the last level is at least half full (p >= m/2), then the left subtree gets all possible nodes: L = 2^h - 1.
    • Otherwise, the left subtree gets fewer nodes: L = 2^h - 1 - (m/2 - p).

  4. Combinatorial Choices: There are C(N-1, L) ways to choose which (N-1) elements go to the left subtree.

  5. Recursion: Recursively compute the number of max heaps for the left and right subtrees.

  6. Dynamic Programming: Use memoization to cache results for each N to avoid redundant computation.

  7. Binomial Coefficient Precomputation: Precompute all required binomial coefficients for efficiency.

  8. Modulo Operation: Since the answer can be large, return the result modulo 1e9+7.

Complexity

  • ⏰ Time complexity: O(N^2) — There are O(N^2) subproblems due to the DP and binomial coefficient table, and each subproblem is computed in O(1) after memoization.
  • 🧺 Space complexity: O(N^2) — O(N^2) for the nCk table, O(N) for the DP array, and O(N) for the log2 array.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

class Solution {
    final long MOD = 1000000007;
    long[] dp;
    long[][] nck;
    int[] log2;

    public int countMaxHeaps(int n) {
        dp = new long[n+1];
        Arrays.fill(dp, -1);
        nck = new long[n+1][n+1];
        for (long[] row : nck) Arrays.fill(row, -1);
        log2 = new int[n+1];
        int currLog = -1, currPow2 = 1;
        for (int i = 1; i <= n; i++) {
            if (currPow2 == i) { currLog++; currPow2 *= 2; }
            log2[i] = currLog;
        }
        return (int)getNumberOfMaxHeaps(n);
    }

    private long getNumberOfMaxHeaps(int n) {
        if (n <= 1) return 1;
        if (dp[n] != -1) return dp[n];
        int L = getL(n);
        long ans = (choose(n-1, L) * getNumberOfMaxHeaps(L)) % MOD * getNumberOfMaxHeaps(n-1-L) % MOD;
        dp[n] = ans;
        return ans;
    }

    private long choose(int n, int k) {
        if (k > n) return 0;
        if (n <= 1 || k == 0) return 1;
        if (nck[n][k] != -1) return nck[n][k];
        long answer = (choose(n-1, k-1) + choose(n-1, k)) % MOD;
        nck[n][k] = answer;
        return answer;
    }

    private int getL(int n) {
        if (n == 1) return 0;
        int h = log2[n];
        int p = n - ((1 << h) - 1);
        int m = 1 << h;
        if (p >= m / 2) return (1 << h) - 1;
        else return (1 << h) - 1 - (m / 2 - p);
    }
}

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Solution:
    def countMaxHeaps(self, n: int) -> int:
        from math import log2
        MOD = 10**9 + 7
        dp = [-1] * (n+2)
        nck = [[-1]*(n+2) for _ in range(n+2)]

        def choose(n, k):
            if k > n: return 0
            if n <= 1 or k == 0: return 1
            if nck[n][k] != -1: return nck[n][k]
            nck[n][k] = (choose(n-1, k-1) + choose(n-1, k)) % MOD
            return nck[n][k]

        def getL(n):
            if n == 1: return 0
            h = int(log2(n))
            p = n - ((1 << h) - 1)
            m = 1 << h
            if p >= m // 2:
                return (1 << h) - 1
            else:
                return (1 << h) - 1 - (m // 2 - p)

        def getNumberOfMaxHeaps(n):
            if n <= 1: return 1
            if dp[n] != -1: return dp[n]
            L = getL(n)
            ans = (choose(n-1, L) * getNumberOfMaxHeaps(L)) % MOD
            ans = (ans * getNumberOfMaxHeaps(n-1-L)) % MOD
            dp[n] = ans
            return ans

        return getNumberOfMaxHeaps(n)