Getting the size of Binary Search Tree
Posted on May 11, 2011
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
This problem demonstrates simple binary tree traversal. Given a binary tree, count the number of nodes in the tree.
Here is the code in c/cpp:
/\* Compute the number of nodes in a tree. \*/
int size(struct node\* node) {
if (node==NULL) {
return(0);
} else {
return(size(node->left) + 1 + size(node->right));
}
}
Find the nth Fibonacci number
Posted on July 5, 2010
(Last modified on August 7, 2020)
| 6 minutes
| Kinshuk Chandra
Problem: Write the code for nth Fibonacci number.
Solution: There are basically two approaches to solving the Fibonacci problem. Lets looks at the definition of Fibonacci series first.
The Fibonacci series is defined as follows
F(n) = 0 for n = 0 1 for n = 1 F(n-1) + F(n-2) for n > 1 So, F(n) = F(n-1)+F(n-2) for n≥2and 1 otherwise.
There are couple of approach to solve this.
[Read More]GCD and LCM
Posted on April 26, 2010
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Finding the GCD
GCD for 60 and 40 is 20: 60 = 40 * 1 + 20
40 = 20 * 2 + 0
LCM for 60 and 40 is 120:
60*40 / 20
Recursive solution for GCD
int gcd(a, b): if b==0: return a return gcd(b, a%b) Iterative solution for GCD
int gcd(a, b): while (b != 0): //swap a with b, and b with a%b temp = a%b a = b b = t return a Finding the LCM
[Read More]Merge Sort
Posted on January 14, 2010
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Mergesort is one of the older algorithms known since 1945. It is very good example of divide and conquer paradigm and is better than other simpler sort algorithms like selection, insertion or bubble sort.
The sorting problem
Input: Array of numbers , unsorted. Eg.
Output : Same numbers sorted in some order, say increasing order. Eg.
So, merge sort algorithm is a recursive algorithm which calls itself on the smaller problem set.
[Read More]Convert integer into a binary number
Posted on January 5, 2010
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
This code will print the binary number for the integer num:
void generatebits(int num) { int temp; if(num!=0) { temp = num % 2; generatebits(num >>= 1); printf("%d",temp); } } int main() { int num; printf("\\nEnter a number\\n"); scanf("%d", &num); printf("\\n\\n"); generatebits(num); return(0); } Writing a function to convert integer to bits-string
For example, if input is 2, the output is “00000000000000000000000000000010” if the system is 32-bit, “0000000000000010” if the system is 16-bit and so on.
[Read More]Binary search on Array - Recursive and iterative
Posted on January 5, 2010
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
There are two basic searching algorithms used. One is the simplest technique and is discussed here.
Here we will discuss the binary search method.
The other search method is the binary search method. The binary search technique is a very fast and a more efficient technique when compared to the linear search method, and gets us the result in O(log n) where n is number of elements. The only requirement for this method is that the input array of elements must be in the sorted order.
[Read More]Euclid's Algorithm : GCD of 2 integers
Posted on January 5, 2010
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
The following example solves a classic elementary problem: “Reduce a given fraction to its lowest terms”, e.g. we want to write 2/3, not 4/6. We solve this problem by finding the greatest common divisor (gcd) of the numerator and the denominator by using the famous approach called Euclid’s algorithm.
C Code
Iterative solution
// Iterative algorithm int gcd(int a, int b) { int temp; while(b) { temp = a % b; a = b; b = temp; } return(a); } Recursive solution
[Read More]Reversing a number
Posted on January 3, 2010
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
int n=12345,m=0;
cout«"Orginal No:“<
while(n>0)
m *= 10;
n /= 10;
cout«”\nRevesed No:“<
Recursive function
int reverse\_num(int n,int m)
{
if(n==0)
return m; //base (exit condition)
m\*=10;
m+=n%10;
return reverse\_num(n/10,m); //recursive call
}
```
How to add two numbers without using the plus operator?
Posted on December 5, 2009
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Actually,
SUM = A XOR B
CARRY = A AND B
Recursive:
int add(int a, int b){
if (!a) return b;
else
return add((a & b) « 1, a ^ b);
}
Iterative
**unsigned long add(unsigned long integer1, unsigned long integer2)
{
unsigned long xor, and, temp;
and = integer1 & integer2; /* Obtain the carry bits */
xor = integer1 ^ integer2; /* resulting bits */
while(and !
[Read More]Calculate pow function
Posted on November 27, 2009
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Lets look at some solutions.
Solution 1 - Using recursion
int pow(int x, int y) { if(y == 1) return x ; return x \* pow(x, y-1) ; } Divide and Conquer C program
/\* Function to calculate x raised to the power y \*/ int power(int x, unsigned int y) { if( y == 0) return 1; else if (y%2 == 0) return power(x, y/2)\*power(x, y/2); else return x\*power(x, y/2)\*power(x, y/2); } /\* Program to test function power \*/ int main() { int x = 2; unsigned int y = 3; printf("%d", power(x, y)); getchar(); return 0; } Time Complexity: O(n)
[Read More]