|
Given an integer N which denotes the number of elements in a binary heap. Check if the binary Heap is completely filled or not.
Examples:
Input: 7
Output: YES
Explanation: At height = 0, no. of elements = 1
At height = 1, no. of elements = 2
At height = 2, no. of elements = 4
Last level is completely filled because at level 2 we need 22 = 4
elements to fill completely and 4 elements are here.
Input: 16
Output: NO
Explanation: At height=0, no. of elements=1
At height = 1, no. of elements = 2
At height = 2, no. of elements = 4
At height = 3, no. of elements = 8
At height = 4, no. of elements = 1
Last level is not completely filled because at level 4
we need 24 = 16 elements to fill completely but here is only 1 element
Input: 31
Output: YES
Approach: The idea here is
In a binary heap, a parent has 2 children. For each level h, number of elements are 2h
Follow the steps below to solve the given problem:
- First find the number of nodes till height h = 20 + 21 + 22 + . . . + 2h.
- Above written series is a geometric progression, so using sum of GP = ( a( rk-1 )/(r-1) ), here a = 20 = 1, r = 2, k = h.
- Therefore sum = 1 * (2h – 1) / (2 – 1) = 2h – 1.
- Height of a binary tree = log2N+ 1.
- Now check if the sum is equal to N or not.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
string isCompletelyFilled(int n)
{
int height = log2(n) + 1;
int sum = pow(2, height) - 1;
if (sum == n)
return "Yes";
return "No";
}
int main()
{
int N = 7;
cout << isCompletelyFilled(N);
return 0;
}
|
Java
import java.util.*;
class GFG
{
static String isCompletelyFilled(int n)
{
int height =(int)(Math.log(n) / Math.log(2)) + 1;
int sum = (int)Math.pow(2, height) - 1;
if (sum == n)
return "Yes";
return "No";
}
public static void main(String[] args)
{
int N = 7;
System.out.print(isCompletelyFilled(N));
}
}
|
Python3
import math
def isCompletelyFilled(n) :
height = int(math.log2(n)) + 1
sum = pow(2, height) - 1
if (sum == n) :
return "Yes"
return "No"
N = 7
print(isCompletelyFilled(N))
|
C#
using System;
public class GFG {
static String isCompletelyFilled(int n)
{
int height = (int)(Math.Log(n) / Math.Log(2)) + 1;
int sum = (int)Math.Pow(2, height) - 1;
if (sum == n)
return "Yes";
return "No";
}
static public void Main()
{
int N = 7;
Console.Write(isCompletelyFilled(N));
}
}
|
Javascript
<script>
function isCompletelyFilled(n)
{
let height = Math.floor(Math.log(n) / Math.log(2)) + 1;
let sum = Math.pow(2, height) - 1;
if (sum == n)
return "Yes";
return "No";
}
let N = 7;
document.write(isCompletelyFilled(N));
</script>
|
Time Complexity: O(logN), time taken by pow is logN
Auxiliary Space: O(1)
|
