Last Digit of exponent(a^b).

This is an editorial for the problem LASTDIG on SPOJ.

The problem asks us to find the last digit of the exponent a^b. It has many different ways to get solution.

Lets discuss three different approaches in solving this problem:

  • 1) Keep on multiplying the number ‘a’ for ‘b’ times and keep tracking the last digit that is to output in the end. Keeping track of last digit here implies, for larger values of ‘a’ and ‘b’, the product could cross the range of int or long.It takes a O(n) complexity. This could take a long time and might result in TLE(Time Limit Exceeded) as the limits in general to such a problem will be given to test for a faster approach that are discussed in other methods discussed below.
  • 2) Another approach to this problem could be this, with worst possible complexity being O(log n). For this we can keep squaring the number ‘a’ till the power(p) it raised to is the closest to ‘b’ and for the remaining (b-p) times, a is to be multiplied and and the last digit is finally printed out. A algorithm for this approach is
    long long int Fast_pow(long long int b, long long int e){
        long long int ans = 1;
        while (e > 0){
            if (e % 2 == 1)
                ans = (ans * b);
            e = e >> 1;
            b = (b * b);
        }
        return ans;
    }
    

    prod%10 is the answer.
    This method runs a lot faster than previous version. But the problem you start realising is for larger values of a and b, we are not allowed to store such big resultant product values in few languages. We can at most store a 64 bit value if we are using C/C++.

  • 3)In this method let us first know few facts that arises in calculating the last digit of a^b. On observing different exponents, we can say these few cases:
    – If last digit of a is ‘0’ or ‘1’ or ‘5’ or ‘6’, then always in powers of those numbers for any case of ‘b'(except b=0), last digit will be same.
    – If last digit of ‘a’ is 2, the sequence {6,2,4,8} follows for mod(4) of ‘b’.
    – If last digit of ‘a’ is 3, the sequence {1,3,9,7} follows for mod(4) of ‘b’.
    – If last digit of ‘a’ is 4, the sequence {6,4} follows for mod(2) of ‘b’.
    – If last digit of ‘a’ is 7, the sequence {1,7,9,3} follows for mod(4) of ‘b’.
    – If last digit of ‘a’ is 8, the sequence {6,8,4,2} follows for mod(4) of ‘b’.
    – If last digit of ‘a’ is 9, the sequence {1,9} follows for mod(2) of ‘b’.
    Note: for b=0, answer should be 1 in any case of ‘a’. So here we can make a switch case program or if-else program to get the answer. This approach has a O(1) complexity.

    Related Problems : Arithmancy Challenge (HackerEarth), Last Digit (SPOJ). In the problem that is asked in SPOJ, you cannot use switch case as it exceeds size limit(700 bytes). In that case try solving it by using a 2D array. It cuts down the size of the code and thus could get an accepted submission. 🙂

Advertisements

Sphere in a Tetrahedron

I came across a question in Codechef(TETRA) and SPOJ(TETRA) named ‘Sphere in a tetrahedron’. The problem asks us to calculate the radius of the sphere that fits into tetrahedron such that all its faces are tangents to the sphere.

With no prior knowledge of such concept I kept searching on net and found some topic to solve this question. That concept says that radius of sphere that could be inscribed in a tetrahedron is

 r = (3 * vol of tetrahedron)/surface area of tetrahedron

Let PQRS be the tetrahedron and a,b,c,d,e,f be 6 edge lengths of that. Let us assume PQ=a, PS=b, PR=c, QS=d, QR=e, RS=f.

Now, according to problem statement, lengths of edges of tetrahedron is given. So for given edge lengths, what would be the volume of tetrahedron?.

Formula for volume is,
volume_of_tetrahedron

Total surface area can be found by summing up area of each triangular face. For area of triangle when given lengths, can be found using
area_of_traingle

Where x,y,z are lengths of triangle and s = (x+y+z)/2.

And finally we can find the result using the formula mentioned earlier.

C code of this problem.

#include<stdio.h>
#include<math.h>
double sq(double x)
{
    return x*x;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t>0)
    {
        double a,b,c,d,e,f; /* 6 edge lengths */
        double vol; /* volume */
        scanf("%lf %lf %lf %lf %lf %lf",&a,&b,&c,&d,&e,&f);
        vol  =  sqrt(4*sq(a)*sq(b)*sq(c)-sq(a)*sq(sq(b)+sq(c)-sq(f))-sq(b)*sq(sq(a)+sq(c)-sq(e))-sq(c)*sq(sq(a)+sq(b)-sq(d))+(sq(b)+sq(c)-sq(f))*(sq(c)+sq(a)-sq(e))*(sq(a)+sq(b)-sq(d)))/12;
        double sa = 0; /* surface area */
        double t1,t2; /* temporary variables */
        double as1,as2,as3,as4; /* area of 4 faces */
        t1 = (a+b+d)/2.0;
        t2 = t1*(t1-a)*(t1-b)*(t1-d);
        as1 = sqrt(t2);
        t1 = (a+c+e)/2.0;
        t2 = t1*(t1-a)*(t1-c)*(t1-e);
        as2 = sqrt(t2);
        t1 = (b+c+f)/2.0;
        t2 = t1*(t1-b)*(t1-c)*(t1-f);
        as3 = sqrt(t2);
        t1 = (d+e+f)/2.0;
        t2 = t1*(t1-d)*(t1-e)*(t1-f);
        as4 = sqrt(t2);
        sa = as1+as2+as3+as4;
        float r = 3.0*vol/sa;
        printf("%.4lf\n",r);
        t--;
    }
    return 0;
}

Approach to solve Minesweeper Master

This problem(Minesweeper Master) has been asked in Google Codejam qualification round 2014. You can view the problem statement here Minesweeper Master.

The problem in short could be explained as, for a given number of rows(r) and columns(c) in a minesweeper grid, we need to prepare a layout that consists of (m) number of mines. The mines are to be represented by ‘*’, empty spaces are to be denoted by ‘.’.

Our layout should be such that we need to win in one click(Hoping you played the game before. Else it is described in the question). We denote the position that is to be clicked on the layout as ‘c’.

An approach to crack this problem:

Remember there may be number of layouts possible for a given set of number of rows(r), number of columns(c) and number of mines(m).

A prologue for our approach to this problem..

The positions on the layout where a mines can be placed or can be clicked are referred as blocks.
Keep in mind the constraint on number of mines is always atleast one less that r*c(total number of blocks).
In all the cases the block that is clicked at the end of making of layout would be the bottom most-right most block.

Here lets start..

Considering different cases,

1)
If either number of rows or number of columns(or both) is 1.

This case has a solution for whatever might the other attribute is. Remember that number of mines that would be in the layout are always less than r*c(that would be atleast one less than total number of blocks.)

Few cases for sample :

	1 4 3  
	4 1 2  
	1 1 0

Solutions for above :

	Case #1:
	***c
	Case #2:
	*
	*
	*
	c
	Case #3:
	c

2) If number of columns are two and number of mines are not one less than total number of blocks.

There are few subcases in this.

i) If number of mines are odd, it is never possible to get a solution.
ex:

	      5 2 3

lets say solution is

	      **
	      *.
	      ..
	      ..
	      .c

But this is wrong. Because on clicking at a position ‘c'(which is most optimal) we get it like

	      **
	      *.
	      11
	      00
	      00

Which is obviously not a solution since we are unable to win in one click.
ii) If number of mines is 2 less than total number of blocks, it is also not possible
ex:

	      5 2 8

lets say solution is

	      **
	      **
	      **
	      **
	      .c

On clicking at position marked ‘c’ we get

	      **
	      **
	      **
	      **
	      .2

So even this condition fails.

iii) In any other case a solution is possible.
ex:

	      5 2 4

Solution is

	      **
	      **
	      ..
	      ..
	      .c

on clicking at position marked ‘c’ we get

	      **
	      **
	      22
	      00
	      00

Which is a perfect solution as we can win in one click.

3) A similar cases are possible for if number of rows are two.

There are few subcases in this.

i) If number of mines are odd, it is never possible to get a solution.
ex:

 	      2 5 3

lets say solution is

	      **...
	      *...c

But this is wrong. Because on clicking at a position ‘c'(which is most optimal) we get it like

	      **100
	      *.100

Which is obviously not a solution since we are unable to complete the game in one click.

ii) If number of mines is 2 less than total number of blocks, it is also not possible
ex:

	      2 5 8

lets say solution is

	      ****.
	      ****c

On clicking at position marked ‘c’ we get

	      ****.
	      ****2

So even this condition fails.

iii) In any other case a solution is possible.
ex:

	       2 5 4

Solution is

	       **...
	       **..c

on clicking at position marked ‘c’ we get

	       **200
	       **200

Which is a perfect solution as we can win in one click.

4) If number of mines given is one less than total number of blocks.

Marking all the blocks leaving one as containing mines(‘*’), and the remaining with ‘c’ so that it is to be clicked. We are considering bottom-right block is clicked and so mark all other as ‘c’.

sample cases:

		input
	
		2 5 9
		4 4 15
	
		output
	
		Case #1:
		*****
		****c
		Case #2:
		****
		****
		****
		***c

5) Rest all cases.

Here for a better approach, mines are arranged in first r-3 rows in horizontal manner starting from left in every row. For the last 3 rows, they are arranged in vertical manner starting from top to bottom filling from left most column first and moving towards right.

i) A case in horizontal arranging
( If the last mine is to be placed in a block in the ‘c-1’th column.)

That would be a wrong approach. Lets see that case in a sample example for say

                6 5 9

Solution would be

	    	*****
	    	****.
	    	.....
	    	.....
	    	.....
	    	....c

But on clicking the block having ‘c’, we remain with

		*****
		****.
		23321
		00000
		00000
		00000

So on setting an offset for such a case, we can make place the last mine in first column of next row.( Note that there could be only two positions possible for such a case. First column – next row, or first column – last row, as we will be having c in last column- last row).

One of the correct approach is

		*****
		***..
		*....
		.....
		.....
		....c

On clicking on ‘c’ would turn

		*****
		***42
		*4210
		11000
		00000
		00000
		00000

ii) Now while placing mines in last 3 rows(placing them vertically as discussed above).
( A similar case just like above, that is if the last element has to be placed in second last row.)

It would be a wrong approach if we do not make an offset and correct that. Lets see a case

                6 5 20

Solution would be

	    	*****
	    	*****
	    	*****
	    	**...
	    	**...
	    	*...c

On clicking the block having ‘c’, we remain with

		*****
		*****
		*****
		**432
		**200
		*.100

A wrong solution indeed. So similar to previous we can make an offset and let the last mine appear in 3rd last row of next column.

		*****
		*****
		*****
		***..
		*....
		*...c

On clicking ‘c’,

		*****
		*****
		*****
		***42
		*5210
		*2000

A correct approach!!!

Here we can be sure that you will not cross the array boundary like you may not got to a[r-3][c] (‘0’ notation) position. Because that case implies you have (r*c)-1 number of mines to which solution has been already set.

iii) If any one block surrounding ‘c’ are having a mine.

Lets see this case with an example.

    		6 5 28

output is

	    	*****
	    	*****
	    	*****
	    	*****
	    	****.
	    	****c

So in this case on clicking on ‘c’ we are left with,

	    	*****
	    	*****
	    	*****
	    	*****
	    	****.
	    	****2

Game here could not be completed in one step, so there will be no solution. We can here again create an offset for searching if any of the three blocks and if true then print out ‘Impossible’.

Here again we may note that the case in which all three surrounding blocks having a mine is already cleared.

Here ends all the possible cases that may arise. Thus framing a perfect code from this algorithm we will be able to crack the problem.

 

Here is my code using above algorithm.

#include <stdio.h>

int main()
{
    int t;
    scanf("%d",&t);
    int turn =1;
    while(turn<=t)
    {
        int r,c,m;
        scanf("%d %d %d",&r,&c,&m);
        char a[60][60]={'.'};
        int i=0,j=0;
        for(i=0;i<r;i++) //initiating matrix with '.'
        {
            for(j=0;j<c;j++)
            {
                a[i][j]='.';
            }
        }
        int mines=m;
        int flag=0;  //at the end if flag is still zero, then the case is impossible.
        
        if(r==1 || c==1) // if either number of rows or number of columns is one. This case would always get accepted.
        {
            for(i=0;i<r;i++)
            {
                for(j=0;j<c;j++)
                {
                    if(mines>0)
                    {
                        a[i][j]='*';
                        mines--;
                    }
                    else break;
                }
            }
            a[r-1][c-1]='c';
            flag=1;
            printf("Case #%d:\n",turn);
            for(i=0;i<r;i++)
            {
                for(j=0;j<c;j++)
                {
                    printf("%c",a[i][j]);
                }
                printf("\n");
            }
            goto imp;
        }

        if(c==2 && !(m == (r*c)-1))  //If number of columns is 2, and m is not equal to one less than total number of blocks
        {
            if(m%2==1)  //If number of mines are odd in this case, it would never be possible.
            {
                goto imp;
            }
            
            if(m>(r*c)-4)  //If (r*c)-4 < number of mines < (r*c)-1
            {
                goto imp;
            }
            
            for(i=0;i<r;i++)  //all remaining cases here will be possible.
            {
                for(j=0;j<c;j++)
                {
                    if(mines>0)
                    {
                        a[i][j]='*';
                        mines--;
                    }
                    else break;
                }
            }
            a[r-1][c-1]='c';
            flag=1;
            printf("Case #%d:\n",turn);
            for(i=0;i<r;i++)
            {
                for(j=0;j<c;j++)
                {
                    printf("%c",a[i][j]);
                }
                printf("\n");
            }
            goto imp;
        }

        if(r==2 && !(m == (r*c)-1))  //If number of rows is 2, and m is not equal to one less than total number of blocks
        {
            if(m%2==1)  //If number of mines are odd in this case, it would never be possible.
            {
                goto imp;
            }
            
            if(m>(r*c)-4)  //If (r*c)-4 < number of mines < (r*c)-1
            {
                goto imp;
            }
            
            for(j=0;j<c;j++)  //all remaining cases here will be possible.
            {
                for(i=0;i<r;i++)
                {
                    if(mines>0)
                    {
                        a[i][j]='*';
                        mines--;
                    }
                    else break;
                }
            }
            a[r-1][c-1]='c';
            flag=1;
            printf("Case #%d:\n",turn);
            for(i=0;i<r;i++)
            {
                for(j=0;j<c;j++)
                {
                    printf("%c",a[i][j]);
                }
                printf("\n");
            }
            goto imp;
        }
        
        if(mines == (r*c)-1)  //if number of mines is one less than total number of blocks. Solution is always possible.
        {
            for(i=0;i<r;i++)
            {
                for(j=0;j<c;j++)
                {
                    a[i][j]='*';
                }
            }
            a[r-1][j-1]='c';
            flag=1;
            printf("Case #%d:\n",turn);
            for(i=0;i<r;i++)
            {
                for(j=0;j<c;j++)
                {
                    printf("%c",a[i][j]);
                }
                printf("\n");
            }
            goto imp;
        }

        int h1=0;
        for(i=0;i<r-3;i++)  //rest all cases
        {
            for(j=0;j<c;j++)
            {
                if(mines==1 && j==c-2)  //if last mine is to be filled in second last column, it would be wrong case. Setting offset.
                {
                    h1=1;
                    break;
                }
                if(mines>0)
                {
                    a[i][j]='*';
                    mines--;
                }
            }
            if(h1==1)
                break;
        }

        if(h1==1)  // if last mine is to be placed in second last column, making a correct apprach.
        {
            a[i+1][0]='*';
            mines--;
        }

        int h2=0;
        for(j=0;j<c;j++)
        {
            for(i=r-3;i<r;i++)
            {
                if(mines==1 && i==r-2)  ////if last mine is to be filled in second last row, it would be wrong case. Setting offset.
                {
                    h2=1;
                    break;
                }
                if(mines==1 && j==c-2)
                {
                    goto imp;
                }
                if(mines>0)
                {
                    a[i][j]='*';
                    mines--;
                }
                else break;
            }
            if(h2==1)
                break;
        }

        if(h2==1)  // if last mine is to be placed in second last row, making a correct apprach.
        {
            a[r-3][j+1]='*';
            mines--;
            if(j+1==c-2)
                goto imp;
        }

        a[r-1][c-1]='c';

        if(a[r-2][c-2]=='*' || a[r-1][c-2]=='*' || a[r-2][c-1]=='*') //If 'c' is surrounded by mine
            goto imp;

        flag=1;
        printf("Case #%d:\n",turn);  //printing out the solution
        for(i=0;i<r;i++)
        {
            for(j=0;j<c;j++)
            {
                printf("%c",a[i][j]);
            }
            printf("\n");
        }

        imp:
        if(flag==0)  //printing out impossible if flag=0
        {
            printf("Case #%d:\n",turn);
            printf("Impossible\n");
        }

        turn++;
    }


    return 0;
}

You could also download complete solution for this link. Download

In C,  a[5] == 5[a]

Yeah!!! Looks funny but true.

In C array indexing is actually defined as

a[i] = *(a+i)

You can also make this as

a[i] = *(i+a)

As from our childhood math, we know, a+i and i+a are equal.

As pointers are memory addressing, a[i] that is defined as *(a+i) is address of i elements further from address of “a”. This is also equal to “a” from i elements from beginning of address space (i+a).

And yes

"ABCD"[2] == 2["ABCD"] == 'C'

Booth’s Algorithm for multiplication of signed binary numbers.

Booth’s Multiplication Algorithm is used to multiplication of two signed binary numbers. This algorithm was invented by Andrew Donald Booth in 1950. All it includes are addition of binary numbers and right shift operation.

Let us discuss a C program that calculates and displays multiplication of two signed binary numbers using Booth’s Algorithm in tabular form.

In the discussion let us first know Booth’s Algorithm.

For a given two numbers ‘q’ and ‘m’. Convert them to binary ‘Q’ and ‘M’. Also find 2’s compliment of ‘M’ as we need to use the value of -M.(Note that in signed binary -M is 2’s compliment of M).

Draw a table with 4 columns. First step no., second P(the value in accumulator), third multiplicand(Q), and fourth is previous state(Q-1).

Booth’s Algorithm has ‘N’ number of steps where ‘N’ is size of binary numbers that are being multiplied.(Remember that we need to take them in same size. If they are not same, make them zero by adding leading zeros or ones according to the number).

Set step no. to 0. Set P initially to zero. Fill in the Q register value equal to multiplicand. And Q-1 column as zero.

Now follow the following steps on comparing values of LSB of Q an Q-1.

Q – Q-1         Action
0 – 0        Right Shift.
0 – 1        Add M to P and Right Shift.
1 – 0        Add -M to P and Right Shift.
1 – 1        Right Shift.

The final product is combination of P-Q in signed binary number.

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

void rightShift();

int main()
{
    printf("\n");
    printf(" BOOTH's Algorithm\n"); //Printing out Booth's Algorithm for multiplication of signed binary numbers
    printf("0-0 Right Shift.\n");
    printf("0-1 Add M to P. Right Shift.\n");
    printf("1-0 Add -M to P. Right Shift.\n");
    printf("1-1 Right Shift.\n");
    printf("\n");
    printf("Enter two numbers that are to be multiplied : ");//taking two numbers as inputs
    int a,b;
    scanf("%d %d",&a,&b);
    int ap=a,bp=b;
    if(ap<0) //checking if any of the inputs are -ve
        ap*=-1;
    if(bp<0) bp*=-1; if(bp>ap) //taking greater VALUE as multiplicand
    {
        ap=bp+ap-(bp=ap);
        a=b+a-(b=a);
    }
    int t1=ap,t2=bp;
    int ab[35]={};
    int bb[35]={};
    int i=0;
    while(t1>0)
    {
        ab[i]=t1%2;
        i++;
        t1/=2;
    }
    ab[i]=0;
    int j=0;
    while(t2>0)
    {
        bb[j]=t2%2;
        j++;
        t2/=2;
    }
    while(j<=i) //equating bits to previous(ab) binary number(ab will either be larger or equal to bb).
        bb[j++]=0;
    int nb=i+1; //nb is number of bits
    i=0;j=0;
    while(i<nb/2) //converting VALUES to binary
    {
        ab[i]=ab[nb-i-1]+ab[i]-(ab[nb-i-1]=ab[i]);
        i++;
    }
    i=0;
    while(i<nb/2) { bb[i]=bb[nb-i-1]+bb[i]-(bb[nb-i-1]=bb[i]); i++; } int x[35]={0}; int y[35]={0}; i=0; if(a>=0) //taking actual binary numbers
    { //x is multiplicand and y is multiplier
        while(i<nb)
        x[i]=ab[i+++1];
    }
    else //2's complimant conversion
    {
        while(i<nb) { if(ab[i]==0) x[i]=1; else x[i]=0; i++; } i=1; x[nb-i]++; while(x[nb-i]==2) { x[nb-i]=0; i++; x[nb-i]++; } } i=0; if(b>=0)
    {
        while(i<nb)
            y[i]=bb[i+++1];
    }
    else //2's complimant conversion
    {
        while(i<nb) { if(bb[i]==0) y[i]=1; else y[i]=0; i++; } i=1; y[nb-i]++; while(y[nb-i]==2) { y[nb-i]=0; i++; y[nb-i]++; } } printf("\n"); //output starts here printf("Multiplicand (Q) %d -> ",a);
    i=0;
    while(i<nb) printf("%d",x[i++]); printf(" and Multiplier (M) %d -> ",b);
    i=0;
    while(i<nb)
        printf("%d",y[i++]);
    printf("\n");
    i=0;
    int ym[35]={0}; //calculating -ve of multiplier. we use that in Booth's algorithm. ym=-y .
    if(b<0)
    {
        while(i<nb)
        ym[i]=bb[i+++1];
    }
    else
    {
        while(i<nb) { if(bb[i]==0) ym[i]=1; else ym[i]=0; i++; } i=1; ym[nb-i]++; while(ym[nb-i]==2) { ym[nb-i]=0; i++; ym[nb-i]++; } } printf("we use -(M) i.e. %d -> ",-b);
    i=0;
    while(i<nb)
        printf("%d",ym[i++]);
    printf("\n");
    int q0=0;
    int p[35]={0}; //p here is value that is stored in accumulator. initially set to zero.
    int steps=nb;
    printf("\n");
    printf("Step No. "); //title of columns.
    i=0;
    while(i<nb)
    {
        if(i*2==nb || i*2==nb-1)
        printf("P");
        else
        printf(" ");
        i++;
    }
    printf(" ");
    i=0;
    while(i<nb)
    {
        if(i*2==nb || i*2==nb-1)
            printf("Q");
        else
            printf(" ");
        i++;
    }
    printf(" Q-1");
    printf("\n");
    j=0;

    while(steps--) //counting down steps.
    { // Booth's algorithm has steps that is equal to no. of bits in multiplier or multiplicand
        printf("%d         ",j++);
        i=0;
        while(i<nb)
            printf("%d",p[i++]);
        printf(" ");
        i=0;
        while(i<nb)
            printf("%d",x[i++]);
        printf(" ");
        printf("%d\n",q0);
        if(x[nb-1]==0 && q0==0) //0-0 condition
        {
            q0=x[nb-1];
            rightShift(p,x,nb);
        }
        else if(x[nb-1]==0 && q0==1) //0-1 condition
        {
            printf("        + ");
            i=0;
            while(i<nb)
                printf("%d",y[i++]);
            i=0;
            while(i<nb)
            {
                p[nb-i-1]+=y[nb-i-1];
                if(p[nb-i-1]==2)
                {
                    p[nb-i-1]=0;
                    if(nb-i-1!=0)
                    p[nb-i-2]++;
                }
                if(p[nb-i-1]==3)
                {
                    p[nb-i-1]=1;
                    if(nb-i-1!=0)
                    p[nb-i-2]++;
                }
                i++;
            }
            printf("\n          ");
            i=0;
            while(i<nb)
                printf("%d",p[i++]);
            printf("\n");
            q0=x[nb-1];
            rightShift(p,x,nb);
        }
        else if(x[nb-1]==1 && q0==0) //1-0 condition
        {
            printf("        + ");
            i=0;
            while(i<nb)
                printf("%d",ym[i++]);
            i=0;
            while(i<nb)
            {
                p[nb-i-1]+=ym[nb-i-1];
                if(p[nb-i-1]==2)
                {
                    p[nb-i-1]=0;
                    if(nb-i-1!=0)
                    p[nb-i-2]++;
                }
                if(p[nb-i-1]==3)
                {
                    p[nb-i-1]=1;
                    if(nb-i-1!=0)
                    p[nb-i-2]++;
                }
                i++;
            }
            printf("\n          ");
            i=0;
            while(i<nb)
                printf("%d",p[i++]);
            printf("\n");
            q0=x[nb-1];
            rightShift(p,x,nb);
        }
        else if(x[nb-1]==1 && q0==1) //1-1 condition
        {
            q0=x[nb-1];
            rightShift(p,x,nb);
        }
    }
    printf("%d         ",j);
    i=0;
    while(i<nb)
        printf("%d",p[i++]);
    printf(" ");
    i=0;
    while(i<nb)
        printf("%d",x[i++]);
    printf(" ");
    printf("%d\n",q0);
    printf("\n");

    printf("Product in signed binary number is : "); //printing out the product. it will be in signed binary representation
    i=0;
    while(i<nb)
        printf("%d",p[i++]);
    i=0;
    printf(" ");
    while(i<nb)
        printf("%d",x[i++]);
    printf("\n\n");
    return 0;
}

void rightShift(int p[],int x[],int nb)
{
    int i=0;
    while(nb-i-1)
    {
        x[nb-i-1]=x[nb-i-2];
        i++;
    }
    x[0]=p[nb-1];
    i=0;
    while(nb-i-1)
    {
        p[nb-i-1]=p[nb-i-2];
        i++;
    }
}

The result thus is combination of binary numbers in P and Q.

A brief explanation of what is done in the program:

Taken two decimal numbers, converted them to binary numbers, also found out 2’s compliment of multiplier(M). On each step comparing the values of LSB of Q and Q-1 on following steps as in Booth’s Algorithm completed all N steps. Note, after N steps, the value of Q will be same as when started. Right Shifts are to be done in such a way that MSB of P remains same as previous, LSB of P is MSB of Q, LSB of Q is Q-1 for new state.

Thus on completion of N steps, we get the product.

Example: for multiplying -5 and 10, above code gives following output

BOOTH's Algorithm
0-0   Right Shift.
0-1   Add M to P. Right Shift.
1-0   Add -M to P. Right Shift.
1-1   Right Shift.

Enter two numbers that are to be multiplied : -5 10

Multiplicand (Q) 10 -> 01010 and Multiplier (M) -5 -> 11011
we use -(M) i.e. 5 -> 00101

Step No.    P      Q    Q-1
0         00000  01010  0
1         00000  00101  0
        + 00101
          00101
2         00010  10010  1
        + 11011
          11101
3         11110  11001  0
        + 00101
          00011
4         00001  11100  1
        + 11011
          11100
5         11110  01110  0

Product in signed binary number is : 11110 01110

What does return 0 signifies?

A very common doubt of a beginner is, “For what is the return 0 at the end of main function used?”

Here we shall discuss what the return 0 signifies. Let us first know that the main() can be declared in different formats.

void main()
int main()
main()
char main()

And yes you can define with other existing data types and all those are accepted by C compiler. Returning a value makes sense as each function need to return some value that belongs to the data type of that function. So we declare a return statement at the end of main() function to return a value that belongs to data type main() is defined with.

And so we actually return ‘0’ at the end of int main(). Even main() is considered as int main() as default and hence you can return integer values at the end of main(). And yes you could also return any number other than ‘0’ for int main() and that would work perfect.

However it is not any compulsion of defining return statement as most of the compilers by default return ‘0’ value at the end of main() function.

A void main() does not return any value, since data type ‘void’ mean to have no value in it.

Edit: (From the comment by ythej)
Returning 0 for main function signifies that program is executed without errors. And returning non zero values implies program has some errors. However in our local machines, this does not produce any error for returning any value from main function. But when we submit some code on online compilers, they produce a run time error(NZEC) signifying program has got some error at the time of execution(error according to compiler). NZEC itself abbreviates for Non-Zero-Exit-Code, implies main returns a non zero value.

Hello World!

As in general every programmer starts with this simple code, I would here welcome the world to my blog.

#include <stdio.h>

int main()
{
    printf("Hello World!\n");
    printf("Welcome to my blog!\n");
    return 0;
}