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

/*
    Name        : Rasesh Mori
    Roll        : 201105518
    Assignment  : 0
    Input       : Number for which power of 2 is to be found(2^n) (0<=n<=100)
    Ouput       : Last 10 digits of 2^n
    Description : Case 1: input<15(i.e. 2^n can be stored in integer variable)
                  * Find power by multiplying 2 n times

              Case 2: input>=15
                  * Store the result in an array of 10 numbers such that each array variable stores one digit of output and simulate multiplication
*/


int main()
{
    int powerNum;       //number of which power of 2 is to be found
    int counter;
    int powerValue;     //stores result if result can be accomodated in integer range
    int powerArray[10]; //stores last 10 digits for large numbers
    int index;
    int carry = 0;      //used to store carry for multiplication in array
    int arrayValue;     //temporary storage of calculation
    int prefixZeroFlag = 1; //used while printing final answer to remove initial zeroes


    //Get input
    printf("\n Enter number for which power of 2 is to be found: ");
    if(scanf("%d",&powerNum)==0)
    {
        printf("\n\nInvalid input: Please enter a nuumber in range [0-100]\n\n");
        return 1;
    }


    //Check for correctness of input
    if(powerNum < 0)
    {
        printf("\n\nSorry. This program is designed to find power of 2 for positive numbers only i.e.0<=n<=100. \n\n");
        return 1;
    }
    else if(powerNum > 100)
    {
        printf("\n\nSorry. This program is designed to find power of 2 for positive numbers <=100. \n\n");
        return 1;
    }



    //If result can be accomodated in integer, use traditional method.
    if(powerNum < 15)
    {
        powerValue = 1;

        for(counter = 1; counter <= powerNum; counter++)
        {
            powerValue *= 2;
        }
        printf("\nLast 10 digits of 2^%d is: %d",powerNum, powerValue);
    }
    else    //Perform multiplication storing each digit in array
    {
        index=9;
        powerArray[index] = 1;

        //initialize array to 0
        for(counter=0; counter < 9; counter++)
        {
            powerArray[counter]=0;
        }


        for(counter=1; counter<=powerNum; counter++)
        {
            while(index>=0)
            {
                arrayValue = powerArray[index] * 2 + carry; //Perform multiplication adding previous carry, of any

                carry=0;
                if(arrayValue <= 9)
                {
                    powerArray[index] = arrayValue;
                }                           //If result >9, calculate carry and use in next mul.
                else
                {
                    powerArray[index] = arrayValue % 10;
                    carry = arrayValue / 10;
                }
                index--;
            }

            carry=0;
            arrayValue=0;
            index=9;
        }


        printf("\nLast 10 digits of 2^%d is: ",powerNum);

        for(index=0;index<10;index++)                       //Printing result
          {
            /*if(powerArray[index]==0 && prefixZeroFlag)
                continue;
            else
            {*/
                prefixZeroFlag=0;
                printf("%d",powerArray[index]);
            //}

        }
    }

    printf("\n\n");
    return 0;
}