Find power(n, exp) efficiently

I will discuss three approaches to find power(n, exp). power(n, exp) is defined as
power(2, 4) = 2 * 2 * 2 *2 = 16.


Iterative approach:
Space Complexity = ;
Time Complexity =
   

    result=1;
    for(i=1 ; i<=exp ; i++) {
        result *= n;
    }
    printf("Iterative method: [%d]\n", result);

Divide and Conquer / Recursive approach:

While finding power(2, 20), we know that .
i.e, .
It means that we can find solution for power(n, exp/2) and multiply that value with it again.
...
temp = power(n, exp/2);
power(n, exp) = temp * temp;
...
That is how we can avoid recomputing power(n, exp/2) TWO times.
Space Complexity = [ Used in Stack, while running the program ] ;
Time Complexity = O(log n)

int rec_pow(int n, int exp) {
    int subsoln;
    if (exp==1) {
        return n;
    }

    subsoln = rec_pow(n, exp/2);
    if (exp & 1) {
        // If exp is odd number.
        return n * subsoln * subsoln;
    }


    return subsoln * subsoln;
}

Exponentiation by Squaring / (log n) Iterative Method:
Refer: Wiki: Exponentiation by Squaring
It seems Art of Computer Programming, Volume 2: Semi numerical Algorithms by Donald Knuth ( his books are generally Juggernaut ) has discussed this method in detail. You may refer it ( I have not yet ).



This approach is implementation of the equation shown above.
Space Complexity = O(1) ;
Time Complexity = O(log n)

This code will work only for exp > 0.

    result=1;
    while(exp) {
        if (exp & 1) { // If exp is odd number.
            result *= n;
        }
        exp >>= 1;
        n *= n;
    }
    printf("Exponentiation by Squaring method: [%d]\n", result);

Which one is faster ?

Just found something interesting !!

Problem – 1

for(i=1 ; i<=10000 ; i++){
    for(j=1 ; j<=10 ; j++){
        // Compute A
    }   
}

Problem – 2

for(j=1 ; j<=10 ; j++){
    for(i=1 ; i<=10000 ; i++){
        // Compute A
    }
}

Which one is faster ? Are they both same ?

** Compute A for both takes same time

Print nodes in a Binary Tree [ Level wise ]

There are more then one ways to achieve this. But, the theme is to do BFS. Here is one of them. It is self-explanatory.

#include<stdio.h>
#include<stdlib.h>

struct node{
    int data;

    struct node* left;
    struct node* right;
};

struct node* queuePtr[100];
int front,end;

struct node* getNode () {
    struct node *t = (struct node*) malloc(sizeof(struct node));
    t->left = t->right = NULL;

    return t;
}

void print_BST_levelwise () {
    while (front < end) {
        if (queuePtr[front] != NULL) {
            if (queuePtr[front]->left == NULL && queuePtr[front]->right == NULL) {
                front++;
                continue;
            }
            //if (queuePtr[front]->left != NULL) {
                queuePtr[end++] = queuePtr[front]->left;
            //}
            //if (queuePtr[front]->right != NULL) {
                queuePtr[end++] = queuePtr[front]->right;
            //}
        }
        front++;
    }

    //Done with BFS... Now print
    int i,j,c;
    for(i=0 ; i<end ; i++) {
        if (queuePtr[i] != NULL) {
            printf("%d, ", queuePtr[i]->data);
        } else {
            printf("null, ");
        }
    }
    printf("\n\nLevelwise printing\n");
    c=-1;
    for(i=0 ; i<end ; ) {
        c++;
        printf("Level [%d]:\t\t", c+1);
        for(j=0 ; j<(1<<c) ; j++) {
            if (queuePtr[i] != NULL) {
                printf("%d, ", queuePtr[i]->data);
            } else {
                printf("null, ");
            }
            i++;
        }
        printf("\n");
    }
}

int main () {
    struct node* n1 = getNode();
    struct node* n2 = getNode();
    struct node* n3 = getNode();
    struct node* n4 = getNode();
    struct node* n5 = getNode();
    struct node* n6 = getNode();

    n1->data = 1;
    n1->left = n2;
    n1->right = n3;

    n2->data = 2;
    n2->left = n4;
    n2->right = n5;

    n3->data = 3;
    n3->left = NULL;
    n3->right = n6;

    n4->data = 4;
    n5->data = 5;
    n6->data = 6;


    /*  
        How does the Tree look ?


                                     1
                                   /   \
                                  2     3
                                /   \     \
                               4     5     6

    */

    front=end=0;
    queuePtr[end++] = n1;
    
    print_BST_levelwise();
    free(n1);
    free(n2);
    free(n3);
    free(n4);
    free(n5);
    free(n6);

    return 0;
}

Print Left and Right View of a Binary Tree

I will be putting some of interesting problems of Data-Structure and Algorithms that I encounter during my reading or while having some interesting discussions with my friends.

Today, I will post a problem on "How to print the left view and right view of a Binary Tree".

    Left View or Right View of a Binary Tree is a list of nodes visible if we see this tree from left side or a right side respectively. For example, for the Binary Tree shown in C program below, Left-View is {1 2 4 7 8 9 10 11} and Right-View is {1 3 6 7 8 9 10 12}. 

Approach:

    We do a Breadth First Search (BFS) on given binary tree and while doing the BFS on it, we maintain the level info for each node. Now for the left-view, we note the node info in left-view-array when we make our first move to next level. Similarly for the right-view, we note the node info in right-view-array when we leave a given level and are moving to next level. Last node in BFS is always the last node in Right-view !!

#include<stdio.h>
#include<stdlib.h>

#define MAX 100

struct node{
    int data;

    struct node* left;
    struct node* right;
};

struct node* queuePtr[MAX];
int levels[MAX], leftView[MAX], rightView[MAX];
int front, end, lc, rc;

struct node* getNode () {
    struct node *t = (struct node*) malloc(sizeof(struct node));
    t->left = t->right = NULL;

    return t;
}

int isLast(int index) {
    return ( (index+1) == end) ? 1 : 0 ;
}

// To be called once node with index is expanded
void isCand(int index) {
    if (index==0) {
        leftView[lc++] = queuePtr[index]->data;
        rightView[rc++] = queuePtr[index]->data;

        return;
    }
    if (levels[index] > levels[index-1]) {
        leftView[lc++] = queuePtr[index]->data;
    }
    if ( !isLast(index) && (levels[index+1] > levels[index]) ) {
        rightView[rc++] = queuePtr[index]->data;
    } else if (isLast(index)) {
        rightView[rc++] = queuePtr[index]->data;
    }
}

void print_Left_and_Right_View() {
    int i;

    lc = rc = 0;
    levels[front] = 0;
    while (front < end) {
        if (queuePtr[front] != NULL) {
            if (queuePtr[front]->left != NULL) {
                levels[end] = levels[front]+1;
                queuePtr[end++] = queuePtr[front]->left;
            }
            if (queuePtr[front]->right != NULL) {
                levels[end] = levels[front]+1;
                queuePtr[end++] = queuePtr[front]->right;
            }

           isCand(front); 
        }
        front++;
    }

    printf("Left  View : ");
    for(i=0 ; i<lc ; i++) {
        printf("%d ", leftView[i]);
    }

    printf("\nRight View : ");
    for(i=0 ; i<rc ; i++) {
        printf("%d ", rightView[i]);
    }
    printf("\n");
}

int main () {
    struct node* n1  = getNode();
    struct node* n2  = getNode();
    struct node* n3  = getNode();
    struct node* n4  = getNode();
    struct node* n5  = getNode();
    struct node* n6  = getNode();
    struct node* n7  = getNode();
    struct node* n8  = getNode();
    struct node* n9  = getNode();
    struct node* n10 = getNode();
    struct node* n11 = getNode();
    struct node* n12 = getNode();

    n1->data = 1;
    n1->left = n2;
    n1->right = n3;

    n2->data = 2;
    n2->left = n4;
    n2->right = n5;

    n3->data = 3;
    n3->left = NULL;
    n3->right = n6;

    n4->data = 4;

    n5->data = 5;
    n5->right = n7;

    n6->data = 6;

    n7->data = 7;
    n7->left = n8;

    n8->data = 8;
    n8->right = n9;

    n9->data = 9;
    n9->right = n10;

    n10->data = 10;
    n10->left = n11;
    n10->right = n12;

    n11->data = 11;
    n12->data = 12;

    /*
        How does the Tree look ?


                                     1
                                   /   \
                                  2     3
                                /   \     \
                               4     5     6    
                                      \
                                       7
                                      /
                                     8
                                      \
                                       9
                                        \
                                        10
                                       /  \
                                      11  12
    */


    // Main logic starts here ...
    front=end=0;
    queuePtr[end++] = n1;
    
    print_Left_and_Right_View();
    // Main logic ends here ...


    free(n1);
    free(n2);
    free(n3);
    free(n4);
    free(n5);
    free(n6);
    free(n7);
    free(n8);
    free(n9);
    free(n10);
    free(n11);
    free(n12);

    return 0;
} 

Implementation of printf() function

From the time I learned C programming properly, I was thinking how printf takes variable number of arguments. Here, is a small C program which gives a little bit of closer look.



#include<stdio.h>
#include<stdarg.h>

char *convert (unsigned int num, int base) {
    static char buff[33];
    char *ptr;

    ptr=&buff[sizeof(buff)-1];
    *ptr='\0';

    do {
        *(--ptr) = "0123456789abcdef"[num % base];
        num/=base;
    } while (num!=0);

    return(ptr);
}

void myprintf(char * fmt, ...) {
    char *p;
    int i;
    unsigned u;
    char *s;
    char c;
    va_list argp;

    va_start(argp, fmt);

    p=fmt;
    for(p=fmt ; *p != '\0' ; p++) {
        if(*p == '%') {
            p++;

            switch(*p) {
                case 'c' :
                {
                    c=(char)va_arg(argp,int);
                    putchar(c);
                    break;
                }
                case 'd' :
                {
                    i=va_arg(argp,int);
                    if(i<0) {
                        i=-i;
                        putchar('-');
                    }
                    
                    puts(convert(i,10));
                    break;
                }
                case 'o':
                {
                    i=va_arg(argp,unsigned int);
                    puts(convert(i,8));
                    break;
                }
                case 's':
                {
                    s=va_arg(argp,char *);
                    puts(s);
                    break;
                }
                case 'u':
                {
                    u=va_arg(argp, unsigned int);
                    puts(convert(u,10));
                    break;
                }
                case 'x':
                {
                    u=va_arg(argp, unsigned int);
                    puts(convert(u,16));
                    break;
                }
            }
        } else {
            putchar(*p);
        }
    }

    va_end(argp);
}

int main () {
    int i;
    char str[200];
    printf("This an demo of how variable arguments works !!\n");
    printf("Enter any sequence of digits. It should get converted to respective Hexadecimal number : ");
    scanf("%d", &i);
    getchar();
    printf("Enter a string : ");
    scanf("%[^\n]", str);

    // [ ] are kept intentionally.
    myprintf("\nmyprintf: string = [%s], number = [%d] converted to hexadecimal = [%x]\n", str, i, i);

    /*
            $ gcc -Wall myPrint_program.c
            $ ./a.out

            This an demo of how variable arguments works !!
            Enter any sequence of digits. It should get converted to respective Hexadecimal number : 256
            Enter a string : How are u ?
            
            myprintf: string = [How are u ?
            ], number = [256
            ] converted to hexadecimal = [100
            ]
    */

    return 0;
}



How to run on Linux ?
$ gcc -Wall my_printf.c (this will generate a file named a.out)
$./a.out (this will execute the program)

 

 

If you get stuck at any function and its usage, refer man pages for it. ( do "man putchar" for example )