×

# LAALRANG - EDITORIAL( IEMCO16)

Author: Rohit Anand
Tester: Shashank Singh
Editorialist: Rohit Anand

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(R))%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.

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

3049
accept rate: 10%

 2 Thanks for the shortcut approach ! Learnt something new :) answered 13 Nov '16, 19:16 4★renesmee 99●3 accept rate: 50% 2 @renesmee the alternative approach is just observation based!!:) (14 Nov '16, 17:06)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×900
×347
×55
×47
×23

question asked: 13 Nov '16, 17:33

question was seen: 925 times

last updated: 17 Nov '16, 23:30