Implementing your own power function

How many of you have used that pow(a,b) function in your codes? Well, I think most of you would have used it be it in C/C++/Java/Python or any other programing language which provide this inbuilt function in their libraries.
Ever wondered how that function works? or what is the time complexity in which it evaluates a^b ? What if you are asked to evaluate this on your own? What comes to your mind? The basic O(n) complexity solution? i.e multiplying a*a*a*a........ n times to compute? Can you think of a better approach having a time complexity of Olog(n)?
Yes, you can guess that if you are asked to do this in time complexity of O(log(n)) then we may end up applying the binary search. How? Let's see :

It is similar to a basic Divide and Conquer approach i.e dividing the problems into subparts and then solving it using the base case.
Suppose you have to find the value of 13^24.
 You can proceed in this way:
 13^24 = (13^12 )* (13^12)
 13^12 = (13^6)*(13^6)
 13^6 = (13^3)*(13^3)
 13^3 = (13^1) * (13^1) * 13 :-> as 3/2 = 1 (integer division )
 13^1 = (13^0)*(13^0) * 13
 What did you observe?
 if we have to compute a^n and if n is even we have to recursively compute a^(n/2) once and square it  and if n is odd we have to compute the square of  a^(n/2) and multiply it with a
 Therefore we are reducing the search space or say computing space by half which gives us the time complexity of O(log(n)).

int pow(int a, int n)
{
    if(n==0)
   {
      return 1;  //base condition
   }
   int temp = pow(a,n/2);
   if(n%2==0)
   {
       int ans = temp*temp;
      return ans;
   }
   else 
   {
      return (a*temp*temp);
   }
}

Heap in STL

  HEAP DATA STRUCTURE


#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
vector<int>v1;
  v1.push_back(10);
  v1.push_back(5);
  v1.push_back(8);
  v1.push_back(48);
  v1.push_back(20);
  v1.push_back(6);
  v1.push_back(1);


Making Heap 

make_heap(v1.begin(),v1.end());
This will convert this vector into a heap
cout<<v1.front()<<endl;
Sort Heap -> After this the operation the container is sorted and no longer a Heap
sort_heap(v1.begin(),v1.end());
vector<int>::iterator it ;
for(it=v1.begin();it!=v1.end();it++)
{
cout<<*it<<" ";
}
cout<<endl;
Insert new elements in Heap
push_heap() :- This function is used to insert elements into heap. The size of the heap is increased by 1. New element is placed appropriately in the heap.


 pop_heap() :- This function is used to delete the maximum element of the heap. The size of heap is decreased by 1. The heap elements are reorganized accordingly after this operation.
pop_heap() should be followed by a v1.pop_back()  otherwise it won't actually be popped. Coz pop_heap() just shifts the largest element to the end position . pop_back() reduces the size of the heap by one.
 v1.push_back(50);
     
    // using push_heap() to reorder elements
    push_heap(v1.begin(), v1.end());
     
    // Displaying the maximum element of heap
    // using front()
    cout << "The maximum element of heap after push is : ";
    cout << v1.front() << endl;
     
     // using pop_heap() to delete maximum element
    pop_heap(v1.begin(), v1.end());
    v1.pop_back();
     
    // Displaying the maximum element of heap
    // using front()
    cout << "The maximum element of heap after pop is : ";
    cout << v1.front() << endl;

}

output :
48
1 5 6 8 10 20 48
The maximum element of heap after push is : 50
The maximum element of heap after pop is : 6

is_heap() :- This function is used to check whether the container is heap or not. Generally, in most implementations, the reverse sorted container is considered as heap. Returns true if container is heap else returns false.

  is_heap_until() :- This function returns the iterator to the position till the container is the heap. Generally, in most implementations, the reverse sorted container is considered as heap.

Learning Graphs

Representation :

Using adjacency list :


BFS and DFS 
// Program to print BFS traversal from a given source vertex. BFS(int s) 
// traverses vertices reachable from s.
#include<iostream>
#include <list>

using namespace std;

// This class represents a directed graph using adjacency list representation
class Graph
{
    int V;    // No. of vertices
    list<int> *adj;    // Pointer to an array containing adjacency lists

/*
adj = new list[V];
If you use simply list adj[V] system creates an array of list with size V, so your list constructor will get call V times.
new operator allocates memory and invokes the constructor.

So this statement list* adj= new list[V] allocates memory for V times the size of object of class list and invokes constructor of class list V times, and assigns the starting of the memory location to variable adj.

This kind of statement
x = new X[N];
assigns the result of the expression on the right hand side of the = to x.
So, you are dynamically allocating an array of V objects of type list, ans assigning a pointer to the first element to adj.
*/ 

    void DFSUtil(int v, bool visited[]);  // A function used by DFS
public:
    Graph(int V);  // Constructor
    void addEdge(int v, int w); // function to add an edge to graph
    void BFS(int s,int check);  // prints BFS traversal from a given source s
    void DFS(int v);    // DFS traversal of the vertices reachable from v 
};

Graph::Graph(int V)
{
    this->V = V;
    adj = new list<int>[V];
}

void Graph::addEdge(int v, int w)
{
    adj[v].push_back(w); // Add w to v’s list.
}

void Graph::BFS(int s,int  check)
{
    int ans =1;
    // Mark all the vertices as not visited
    bool *visited = new bool[V];
    for(int i = 0; i < V; i++)
        visited[i] = false;

    // Create a queue for BFS
    list<int> queue;

    // Mark the current node as visited and enqueue it
    visited[s] = true; if(s==check){ans =0;}
    queue.push_back(s);

    // 'i' will be used to get all adjacent vertices of a vertex
    list<int>::iterator i;

    while(!queue.empty())
    {
        // Dequeue a vertex from queue and print it
        s = queue.front();
         if(s==check){ans =0;}
        cout << s << " ";
        queue.pop_front();

        // Get all adjacent vertices of the dequeued vertex s
        // If a adjacent has not been visited, then mark it visited
        // and enqueue it
        for(i = adj[s].begin(); i != adj[s].end(); ++i)
        {
            if(!visited[*i])
            {
                visited[*i] = true;
                queue.push_back(*i);
            }
        }//cout<<endl;
    }cout<<endl<<ans<<endl;
}
void Graph::DFSUtil(int v, bool visited[])
{
    // Mark the current node as visited and print it
    visited[v] = true;
    cout << v << " ";

    // Recur for all the vertices adjacent to this vertex
    list<int>::iterator i;
    for (i = adj[v].begin(); i != adj[v].end(); ++i)
        if (!visited[*i])
            DFSUtil(*i, visited);
}

// DFS traversal of the vertices reachable from v. 
// It uses recursive DFSUtil()
void Graph::DFS(int v)
{
    // Mark all the vertices as not visited
    bool *visited = new bool[V];
    for (int i = 0; i < V; i++)
        visited[i] = false;

    // Call the recursive helper function to print DFS traversal
    DFSUtil(v, visited);
}


// Driver program to test methods of graph class
int main()
{

     int nodes, max_edges, origin, destin;
   // cout<<"Enter number of nodes: ";
    cin>>nodes;
    Graph g(nodes);
    max_edges = nodes * (nodes - 1);
    for (int i = 0; i < max_edges; i++)
    {
       
        cin>>origin>>destin;
        
        if((origin == -1) && (destin == -1))
            break;
         g.addEdge(origin, destin);
    }
   
    int verty,checky;
    cin>>verty>>checky;

    g.BFS(verty,checky);
    g.DFS(verty);
}

There is something called as topological sorting , so that you can check which job is scheduled first or next . you can check the order of dfs by  this :

// A C++ program to print topological sorting of a DAG

#include <iostream>

#include <stdio.h>

#include <list>

#include <stack>

using namespace std;

// Class to represent a graph

class Graph

{

    int V;    // No. of vertices'

    // Pointer to an array containing adjacency listsList

    list<int> *adj;

    // A function used by topologicalSort

    void topologicalSortUtil(int v, bool visited[], stack<int> &Stack);

public:

    Graph(int V);   // Constructor

     // function to add an edge to graph

    void addEdge(int v, int w);

    // prints a Topological Sort of the complete graph

    void topologicalSort();

};

Graph::Graph(int V)

{

    this->V = V;

    adj = new list<int>[V];

}

void Graph::addEdge(int v, int w)

{

    adj[v].push_back(w); // Add w to v’s list.

}

// A recursive function used by topologicalSort

void Graph::topologicalSortUtil(int v, bool visited[], 

                                stack<int> &Stack)

{

    // Mark the current node as visited.

    visited[v] = true;

    // Recur for all the vertices adjacent to this vertex

    list<int>::iterator i;

    for (i = adj[v].begin(); i != adj[v].end(); ++i)

        if (!visited[*i])

            topologicalSortUtil(*i, visited, Stack);

    // Push current vertex to stack which stores result

    Stack.push(v);

}

// The function to do Topological Sort. It uses recursive 

// topologicalSortUtil()

void Graph::topologicalSort()

{

    stack<int> Stack;

    // Mark all the vertices as not visited

    bool *visited = new bool[V];

    for (int i = 0; i < V; i++)

        visited[i] = false;

    // Call the recursive helper function to store Topological

    // Sort starting from all vertices one by one

    for (int i = 0; i < V; i++)

      if (visited[i] == false)

        topologicalSortUtil(i, visited, Stack);

    // Print contents of stack

    while (Stack.empty() == false)

    {

        cout << Stack.top() << " ";

        Stack.pop();

    }

}

// Driver program to test above functions

int main()

{

    // Create a graph given in the above diagram

    int V,i,j,k;

    scanf("%d",&V);

    Graph g(V+1);

    for(i=1;i<V;i++)

    {

        scanf("%d%d",&j,&k);

        g.addEdge(j,k);

    }

    cout << "Following is a Topological Sort of the given graph \n";

    g.topologicalSort();

    return 0;

}

There  is a way to traverse a rectangular maze using DFS :

function DFS(x, y, visited, n, m)

    if (x ≥ n OR y ≥ m)

        return

    if(x < 0 OR y < 0)

        return

    if(visisted[x][y] == True)

        return

    visited[x][y] = True

    DFS(x-1, y-1, visited, n, m)

    DFS(x-1, y, visited, n, m)

    DFS(x-1, y+1, visited, n, m)

    DFS(x, y-1, visited, n, m)

    DFS(x, y+1, visited, n, m)

    DFS(x+1, y-1, visited, n, m)

    DFS(x+1, y, visited, n, m)

    DFS(x+1, y+1, visited, n, m)

Difference between a graph and a tree :

In a graph there can be back edge , forward edge , cross edge , tree edge .

DFS of a graph gives you a tree. And if there are more components which are disconnected, then DFS give a tree forest.

1.In a tree  there is aunique  path from every single  vertex to other vertices. Also it is not necessary that degree of all the vertices of a tree is either 1 or 2.

2.There isn't any cycle in a tree.

 How to detect cycle in an undirected graph?

We can either use BFS or DFS. For every visited vertex ‘v’, if there is an adjacent ‘u’ such that u is already visited and u is not parent of v, then there is a cycle in graph. If we don’t find such an adjacent for any vertex, we say that there is no cycle.

3.If we take the sum of all the degrees, each edge will be counted twice. Hence, for a tree with n vertices and n – 1 edges, sum of all degrees should be 2 * (n – 1).

4.Tree has exactly n-1 edges while there is no such constraint for graph.

Babylonian algorithm of finding square root

Finding square root of a number whether its perfect square or not is simple with sqrt(n) function , but what if you have to implement it on your own?

 There are several ways for it. I will tell you about 2 methods:

1. Using Binary Search in O(log N)  time complexity

2. Babylonian Method of O(log(log N)).

1. 
   Using Binary Search

   float squareroot( float n)


{    
    // Base cases
    if (n == 0 || n == 1) 
       return n;

    // Do Binary Search for floor(sqrt(x))
     float start = 1, end = n, ans;   
    while (start <= end) 
    {       
    cout<<start<<"    "<<end<<endl; 
        float mid = (start + end) / 2;

        // If x is a perfect square

      /* It is very important to see that mid*mid can overflow, so rather than doing (mid*mid) do
     if(mid<=x/mid)      */

          if(mid==n/mid)
            return mid;

        // Since we need floor, we update answer when mid*mid is 
        // smaller than x, and move closer to sqrt(x)
         if(mid<=n/mid)
        {
            start = mid + 1;
            ans = mid;
        } 
        else // If mid*mid is greater than x
            end = mid - 1;        
    }
    return (ans+1);
}
   





2.  

float squareRoot(float n)
{
  /*We are using n itself as initial approximation
   This can definitely be improved */
  float x = n;
  float y = 1;
  float e = 0.000001; /* e decides the accuracy level*/
  while(x - y > e)
  {
    x = (x + y)/2;
    y = n/x;
  }
  return x;

}
   

Using Sieve of Eratosthenes with lesser space complexity

This method is called as Segmented Sieve.

The idea of segmented sieve is to divide the range [0..n-1] in different segments and compute primes in all segments one by one. This algorithm first uses Simple Sieve to find primes smaller than or equal to √(n). 

Look I would really like to write about the concept of Segmented Sieve but I think the number of the viewers of my page is few, so what I am gonna do is post some links and code.

Go through this link

#include <iostream>
#include <math.h>
#include <vector>
using namespace std;
void simple_sieve(vector<int> &vec,int num)
{
int range = sqrt(num);
vector<bool>mark(range+1,true);
for(int i =2;i<=sqrt(range);i++) //checking prime numbers <= number^1/2
{
if(mark[i]==true)
{
for(int j=i*2;j<=range;j= j+i)
{
mark[j] = false;
}
}
}
for(int i=2;i<=range;i++)
{
if(mark[i]==true)
{
vec.push_back(i);
}
}

}

void  segmented_sieve(vector<int> &prime , int num)
{
simple_sieve(prime,num);
int lower_range = sqrt(num);
int limit  = lower_range;
int higher_range = 2*lower_range;


while(lower_range<num &&higher_range<=num)
{
vector<bool>mark(limit+1,true);
for(int i =0;i<prime.size();i++)
{
int k = (lower_range/prime[i])*prime[i];
if(k<lower_range){k = k+ prime[i];}
for(int j=k;j<=higher_range;j = j+prime[i])
{
mark[j-lower_range] = false;

}
}
for(int i=lower_range;i<=higher_range;i++)
{
if(mark[i-lower_range]==true)
{
prime.push_back(i);
}
}
lower_range = lower_range + limit;
higher_range = higher_range + limit;
if(higher_range>num){higher_range = num;}
}

}

int main()
{
int num = 1000;
std::vector<int> prime;
segmented_sieve(prime,num);
for (int i = 0; i < prime.size(); ++i)
{
cout<<prime[i]<<endl;
}
}

The usual time complexity of this algorithm is O(N log (log N)).

If you want to perform the Sieve of Eratosthenes in a complexity of O(n) , 

go through This link

pointer arithmetic of an Array and passing a 2D array to a function

Before moving further let's see how a one-dimensional array is stored in a computer memory.
For example, let an array:
                         A = [   3   ][   4   ][   5   ][   6   ][   7   ]      -> value stored in an integer array
                                 200    204     208    212     216         -> these are the address of the memory of the array. As it is an integer array each element has a storage of 4 bytes.

To declare a pointer to a one-dimensional array we simply write:

    int *ptr = A; 
this pointer ptr points to the starting block of the array A. Also, the name of the array i.e A just returns a pointer to the first element of the array.
With the pointer declared we can use pointer arithmetic and dereferencing to access the address and elements of the array.
for example,

print ptr  will give output = 200

print *ptr will give output = 3, i.e the value stored at that memory location (this is called as                                                                                                                                           dereferencing )
print *(ptr +2)  will give us the output 5  as ptr is a pointer to an integer so increasing ptr two times will enhance it to further 8 bytes.

print (ptr +2)  = 208

The language flexibility allows us to use the name of the array as a pointer. Therefore instead of using ptr we can directly use A.
i.e ,

print A = 200
print *A = 3
print *(A+2) = 5
print A+2 = 208

in short,
*(A+i) is same as A[i]
and (A+i) is same as &A[i]

Therefore, ptr = A  but A != ptr .

we can pass a one-dimensional array  in a function as follows:

void myfunction (int *arr)
{
       int n = arr.size();
       cout<<arr[i];
}

int main()
{
   int arr = {1,2,3,4,5,6};
   myfunction(arr);
}

We can do the same thing in a multi-dimensional array. What does it mean when we say multi-dimensional array? A multi-dimensional array is an array of array.
 Let's talk about the two-dimensional array:

Suppose we have a 2-D array:
 B[2][3] = [  [ 2 , 3, 6 ] , [ 4 , 5  ,8  ] ]
                     400             412            -> memory address of the arrays.
Now each element  B[0] and B[1] is an array of integers consisting of three integers each. Hence each block would have a size of 3*4 bytes i.e 12 bytes. Therefore B[0] contains the starting address of the first array  i.e 400  and B[1] contains the starting address of the second array i.e 412.

if we  write,
int *ptr = B ; this will return an error because ptr is a pointer to integer but B is a pointer to a 1-D array of integers.
We can define a pointer to 1-D array of three integers like this:
int (*ptr)[3] = B ;

print B  is same as print (B+0)  and from the above-given statement in 1-D array, (B+i) = &B[i]
 Therefore print B = print  &B[0]  = 400 .

Similarly,
print *B is same as print B[0]  which is equal to a variable name of an array as B[0] is itself a 1-D array, therefore, B[0] will act as a pointer to the address of  first  element of the array B[0] i.e &B[0][0] which is equal to 400.  

Now the output of
print B+1 = &B[1] which is equal to 412 .

print *(B+1) is same as print B[1] which is equal to a variable name of an array as B[1] is itself a   1-D array, therefore, B[1] will act as a pointer to the address of  first  element of the array B[1] i.e &B[1][0] which is equal to 412.

print *(B+1) + 2 = 420. As *(B+1) is a pointer to an integer containing the address of B[1][0] and if we do pointer arithmetic this will occur in terms of bytes. Therefore B[1] + 2 will give the address of B[1][2].

print *(*B + 1) = 3 . As *B returns a pointer to the first integer of the array B[0] and adding 1 to it will take it to the address of B[0][1] which is equal to the value of &B[0][1] again dereferencing it will give the value stored at B[0][1] which is equal to 3.

For 2-D array,
B[i][j] = *(B[i] + j) = *(*(B+i) + j) 

Now passing  a two-dimensional array into a function:

There are several ways of passing a multidimensional array within a function.

1. one of the ways is to use tempelate :

tempelate<int R,int  C>
void myfunc( int (&array)[R][C])
{
     // do stuff
}

2. Another way of doing this is by using simple arithmetic with passing the address of first block :

void myfunc(int n, int m ,int *arr)    // n rows and m columns 
{
    for(i=0;i<n;i++)
     {
           for(j=0;j<m;j++)
           {
               cout<<*((arr+i*n) + j)        // is same as arr[i][j]
           }
     }
}

int main()
{
     // doing stuffs like declaring an array and initializing it
     //calling the function :->
      myfunc(n,m,(int*)arr);
     

}

Update(8/04/2018):
I was using this approach today for a question where I have to manipulate or say modify the contents of the array by using the above-mentioned method of passing the 2d array. Somehow I ended up with segmentation fault every time. Finally, after debugging my code, I realized that the error was in the indexing i.e instead of using "i" I was using "j". So whats the intention of this post? Actually, while I was facing the segmentation fault, I found another method of passing a 2D array to a function after declaring the array dynamically and this is approach is much simpler.



int edit_distance(int **arr,int n,int m,char *source,char *target)
{
   int i=0,j=0,k;
   
    arr[i][j] = 0; // See you can use the arr[i][j] indexing rather than using the pointer arithmetic
   
   for(j=1;j<=m;j++)
   {
      //cout<<"here"<<endl;
        arr[i][j] = j;
       cout<< arr[i][j];
   }
   j = 0;
   for(i=1;i<=n;i++)
   {
        arr[i][j] = i;
   }
   return 3;

}

int main() {
int t;
cin>>t;
while(t--)
{
    int n,m;
    cin>>n>>m;
    char source[n],target[m];
    cin>>source,target;
    int **arr;
    arr = new int*[n+1];
    for(int i =0;i<=n;i++)
    {
    arr[i] = new int[m+1];
    }
    int ans;
    ans = edit_distance(arr,n,m,source,target);
    
    cout<<ans<<endl;
}
return 0;

}

For a better understanding of Headers and Include - C++ OOPS

Go through this link

Divide and Conquer - 1.Karatsuba Algorithm for Multiplication

Hello friends, In this post and following some next posts I would be writing about Divide and Conquer approach of solving problems and famous algorithms which use this approach .
In this post post I am explaining the famous Karatsuba Algorithm for multiplication of number in O(n^1.586) time complexity.

Lets talk about what we actually do when we multiply two numbers. As per I believe, most of us use the basic method of multiplication which has a time complexity of O(n^2).

Something similar to this: 

The above shown multiplication is the simplest basic method for multiplication. But suppose you have to multiply :

3141592653589793238462643383279502884197169399375105820974944592

with 

 2718281828459045235360287471352662497757247093699959574966967627 .

Obviously, If you would go for the basic multiplication method for solving this, it would be a tedious job. That's where the Karatsuba multiplication method comes into play.

In this method we apply the basic principle of divide and conquer i.e divide this multiplication process into smaller sub-process for smaller parts of the number. Suppose we have to multiply 965107 by 102635, both of them are 6-digit numbers i.e a 6 by 6 multiplication.

we can write :

965107 * 102635  = (965000 + 107 ) * (102000 + 635)

                              = (965 * 10^3 + 107  ) * (102 * 10^3 + 635 )

                              = 965 * 102 * 10^6 + 107*635 + 10^3*(965*635 + 102*107) 

 We have reduced one 6 by 6 multilication method into four 3 by 3 multiplication .

The same approach is used in  Karatsuba algorithm :

suppose we have to multiply two n-digit numbers X and Y.

For simplicity assume n is even (where n is the number of digits in X and Y ):

X =  Xl*10^n/2 + Xr    [Xl and Xr contain leftmost and rightmost n/2 bits of X]

Y =  Yl*10^n/2 + Yr    [Yl and Yr contain leftmost and rightmost n/2 bits of Y]

The product of X and Y can be written as :

XY = (Xl*10^n/2 + Xr)(Yl*10^n/2 + Yr)

   = 10^n XlYl + 10^n/2(XlYr + XrYl) + XrYr

Also, XlYr + XrYl = (Xl + Xr)(Yl + Yr) - XlYl- XrYr

So the final result becomes : XY = 10^n XlYl + 10^n/2 * [(Xl + Xr)(Yl + Yr) - XlYl - XrYr] + XrYr

As we need to multiply such large numbers, we store the input in strings and then manipulate them according to our need.

What if the length of two given numbers is not same? In that case we append zeros in front of the numbers which are stored as integers. In case n is odd, we put floor(n/2) bits in left half and ceil(n/2) bits in right half.

The beauty of Karatsuba method is that you can use it for multiplication of numbers of any base ,2,10,16 etc.

The below given code is for multiplication of base 10 numbers. Read it carefully, don't just cram the code :

#include <iostream>

#include <algorithm>

#include <string.h>

#include<stdio.h>

const int MAX_LENGTH = 50000 * 2 + 1;

void add_leading_zeros(char* a, int n) {

  int lena = strlen(a);

  for (int i = lena - 1 + n; i >= n; --i) {

    a[i] = a[i - n];

  }

  a[lena + n] = 0;

  for (int i = 0; i < n; ++i) {

    a[i] = '0';

  }

}

void remove_leading_zeros(char* a) {

  int lena = strlen(a);

  int ind = 0;

  while (ind < lena && a[ind] == '0') {

    ++ind;

  }

  for (int i = ind; i < lena; ++i) {

    a[i - ind] = a[i];

  }

  a[lena - ind] = 0;

}

void sum(char* a, char* b, char* res) {

  int lena = strlen(a);

  int lenb = strlen(b);

  if (lena < lenb) {

    std::swap(a, b);

    std::swap(lena, lenb);

  }

  int toAdd = 0;

  for (int inda = lena - 1, indb = lenb - 1; inda >= 0; --inda, --indb) {

    int x = a[inda] - '0';

    int y = indb >= 0 ? b[indb] - '0' : 0;

    int cur = x + y + toAdd;

    if (cur >= 10) {

      toAdd = 1;

      cur -= 10;

    } else {

      toAdd = 0;

    }

    res[inda] = cur + '0';

  }

  if (toAdd == 1) {

    add_leading_zeros(res, 1);

    res[0] = '1';

  }

}

// assume that a > b

void sub(char* a, char* b, char* res) {

  int lena = strlen(a);

  int lenb = strlen(b);

  //assert(lena >= lenb);

  int toSub = 0;

  for (int inda = lena - 1, indb = lenb - 1; inda >= 0; --inda, --indb) {

    int x = a[inda] - '0';

    int y = indb >= 0 ? b[indb] - '0' : 0;

    if (toSub == 1) {

      x--;

    }

    int cur;

    if (x < y) {

      cur = x + 10 - y;

      toSub = 1;

    } else {

      cur = x - y;

      toSub = 0;

    }

    res[inda] = cur + '0';

  }

}

// returns a * 10^n

void mult10(char* a, int n) {

  int lena = strlen(a);

  if (lena == 1 && a[0] == '0') {

    return;

  }

  for (int i = lena; i < lena + n; ++i) {

    a[i] = '0';

  }

  a[lena + n] = 0;

}

char* CreateArray(int len) {

  char* res = new char[len];

  memset(res, 0, len);

  return res;

}

// add leading zeros if needed

void make_equal_length(char* a, char* b) {

  int lena = strlen(a);

  int lenb = strlen(b);

  int n = std::max(lena, lenb);

  add_leading_zeros(a, n - lena);

  add_leading_zeros(b, n - lenb);

}

void karatsuba(char* x, char* y, char* res) {

  make_equal_length(x, y);

  int len = strlen(x);

  if (len == 1) {

    int val = (x[0] - '0') * (y[0] - '0');

    if (val < 10) {

      res[0] = val + '0';

    } else {

      res[0] = (val / 10) + '0';

      res[1] = (val % 10) + '0';

    }

  } else {

    char* xl = CreateArray(len);

    char* xr = CreateArray(len);

    char* yl = CreateArray(len);

    char* yr = CreateArray(len);

    int rightSize = len / 2;

    int leftSize = len - rightSize;

    strncpy(xl, x, leftSize);

    strcpy(xr, x + leftSize);

    strncpy(yl, y, leftSize);

    strcpy(yr, y + leftSize);

    int maxl = 3 * len;

    char* P1 = CreateArray(maxl);

    char* P2 = CreateArray(maxl);

    char* P3 = CreateArray(maxl);

    karatsuba(xl, yl, P1);

    karatsuba(xr, yr, P2);

    char* tmp1 = CreateArray(maxl);

    char* tmp2 = CreateArray(maxl);

    sum(xl, xr, tmp1);

    sum(yl, yr, tmp2);

    karatsuba(tmp1, tmp2, P3);

    sub(P3, P1, P3);

    sub(P3, P2, P3);

    mult10(P3, rightSize);

    mult10(P1, 2 * rightSize);

    sum(P1, P2, res);

    sum(res, P3, res);

    remove_leading_zeros(res);

    delete[] xl;

    delete[] xr;

    delete[] yl;

    delete[] yr;

    delete[] tmp1;

    delete[] tmp2;

    delete[] P1;

    delete[] P2;

    delete[] P3;

  }

}

int main() {

  char a[MAX_LENGTH], b[MAX_LENGTH];

  scanf("%s\n%s", a, b);

  char* res = CreateArray(MAX_LENGTH);

  karatsuba(a, b, res);

  printf("%s\n", res);

  

  return 0;

}

The answer for multiplication of : 

3141592653589793238462643383279502884197169399375105820974944592

with 

 2718281828459045235360287471352662497757247093699959574966967627

 is :

8539734222673567065463550869546574495034888535765114961879601127067743044893204848617875072216249073013374895871952806582723184

Check the answer using your code. 

Thank you