PROBLEM LINK:
Author: Rohit Anand
Tester: Shashank Singh
Editorialist: Rohit Anand
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
COMBINATORICS,MODULAR MULTIPLICATIVE INVERSE
PROBLEM:
A Binary heap of n nodes is given.You have to answer how many possible permutations of nodes numbered from 1 to n is possible.
QUICK EXPLANATION:
Considering min heap,root is the smallest element. So, 1 will be root.Now, we will divide the remaining nodes into two sub-trees recursively by following the property of binary heap.
EXPLANATION:
We are provided with n nodes of Binary heap.Our aim is to arrange the nodes numbered from 1 to n such that properties of Binary heap remains intact. So, there are many such permutations possible for given
n.
Lets consider min heap.Hence, Root will always be occupied by node 1.Now, the remaining nodes will be divided into left and right sub-trees. Since,Binary heap is a Complete Binary tree, so it will always be inclined towards left and every level except the last will
always be completely filled.Hence, we will first try to fill the left sub-tree and then move the remaining elements in right sub-tree. In order to produce different arrangements, we have to do this process recursively such that property of binary heap is also followed.
Now, we will fill the heap in breadth first fashion ie we will fill the nodes level wise ie the nodes in the lowest level will go to the left-sub tree and then any excess nodes will go to right-sub tree.
Hence for given n number of nodes,the number of binary heaps with n distinct elements can be calculated as,
f(1)=1
f(n)=(n-1CL$f(L)$f®)%MOD, C is combinations and MOD=109+7
where L=No. of elements in Left Sub-tree.
R=No. of elements in Right Sub-tree.
L=2(k−1)−1+min(2(k−1),M)
R=2(k−1)−1+max(0,M−2(k−1))
M=1+N−2k, M is number of nodes in bottom level of tree.
k is level number.
ALTERNATIVE SOLUTION:
There is one observation here.Lets calculate answers for some n values.
n=1, answer=1
n=2, answer=1
n=3, answer=2
n=4, answer=3
n=5, answer=8
n=6, answer=20 and so on.
This actually forms a pattern, which can be calculated using formula,
f(n)= ((n!)/(Product of size of all sub-trees in the heap)).You can verify it.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here
Tester’s solution can be found here
