Number of nodes in a binary tree

A binary tree is a tree in which has every node has two child, except the root node. To calculate the number of nodes one can possibly say, at level 0, there is only one node i.e the root node, and then at each level the number of nodes are in power of 2. So this sums to $1 + 2^1 + 2^2 + 2^3 + ... + 2^k = 2^{k+1} - 1 / 2 - 1 = 2^{k+1} -1$

int main()

Battle with Modulo

Ohh god this modulo and modular is really amazing :P

                                   "You always fear from what you don't understand" 

Modulus is an operation which is used to obtain the remainder when two numbers are divided.

Suppose a = 5 and b = 3, then 

a%b = 5%3 =2

Modulus is distributive over addition, subtraction and multiplication. 

9%6 = (4 + 5) % 6 = 4 % 6 + 5 % 6 = 4 + 5 =9

13%6 = (15 - 2) % 6 = 15 % 6 - 2 % 6 = 3 - 2 = 1

26%6 = (13 * 2) % 6 = 13 % 6 * 2 % 6 = 1 *2 = 2

But the problem comes in case of division.

Consider 4/5 in modulo 6.

i.e 4/5 != (4 % 6) / (5 % 6)                                      (1)

So here comes in picture Modular Inverse.

4/5 in modulo 6 equals 2. Ok now lets see the RHS of (1) in another form

(4 % 6)/(5 % 6) = ((4 % 6) * (5^(-1) % 6))%6        (2)

Since 5 and 6 are coprime(I will explain why is this necessary), So the inverse of 5 exists in ring of 6.

i.e. a number x such that x * 5= 1 mod 6 and that is 5. So 5^(-1)=5

Now taking eq(2) further,

(4*5)%6=20%6=2. Voila the answer is 2. Great!!.

But what if the numbers are not coprime, say 2/4. Lets take this case and solve it in this way

We need an x such that x*2=4 mod 6. 

If x=2 then 4 = 4 mod 6. Wait 5??

Yes if x =5. then 2/5=10 = 4 mod 6, So how come two inverse can exist.

Hence it is necessary that the numbers should be relatively prime (or coprime in short) to each other. Then only the uniqueness of the inverse element can be determined. 

So this leads us to an important conclusion that a number can have either one or no inverse element. The inverse of element can be a or any other integer.

Now comes the important point is how to compute this inverse. Great. Remember Euclid algorithm to compute GCD of two numbers. Yes we can use that and its called Extended Euclid Algorithm.

According to Bezout's Identity, two numbers can be expressed in the form of

                             d = ax + by
where d is the GCD of a and b.

To be continued...

helpfulLinks

These are some of the links which I am documenting here so that it comes in handy when I need them.

Groups : [1]

Greatest Common Divisor

Hi all, In this post I will be telling you about GCD. GCD as you all know stands for Greatest Common Divisor. GCD of two or more integers, when at least one of them is not zero, is the largest positive integer that divides without a remainder. For example GCD of 15 and 25 is 5. The Gcd can be implemented either in iterative or recursive manner.

int gcdi(int a,int b){        //iterative

	while(a!=b){
		if(a>b)
			a = a-b;
		else
			b=b-a;
	}
	return a;
}

int gcdr(int a , int b){			//recursive

if(b>a)return gcdr(b,a);
if(b==0)return a;
else
	return gcdr(b,a%b);
}

The STL algorithm library implements an inbuilt function named __gcd(a,b). gcd(a,b), where a and b are not both zero, may be defined as the smallest positive integer d for which can be written in the form d=a.p+b.q where p and q are integers.

echo "Hello!!!"

#include <bits/stdc++.h>
using namespace std;

int main(){
	cout<<"Hello World\n";
	return 0;
}