Ways to form Max Heap

• Time : O(n^2)
• Space : O(n^2)

c++

long long ncr[111][111];
long long mod = 1e9 + 7;
long long dp[111] = {1,1,};
long long dpp = 2;

long long nCr(int n, int r) {
    if(r > n - r) return nCr(n, n - r);
    if(r == 0) return 1;
    if(ncr[n][r]) return ncr[n][r];
    return ncr[n][r] = (nCr(n-1,r-1) + nCr(n-1,r)) % mod;
}

long long helper(int n) {
    if(n == 1) return 0;
    long long h = log2(n), ma = 1<<h, now = n - (ma - 1);
    return ma - 1 - (now >= (ma / 2) ? 0 : ma / 2 - now);
}
int Solution::solve(int A) {
    while(dpp <= A) {
        int l = helper(dpp);
        dp[dpp] = nCr(dpp-1,l) * dp[l] % mod * dp[dpp-1-l] % mod;
        dpp++;
    }
    return dp[A];
}