Multiplying large numbers in C/C++

Working with large numbers in C/C++ is always a problem. Those who have knowledge in Java/python tend to code in these languages for those particular problems. (Java has a BigInteger class where in there is no limit for integer range you work on. Python doesn’t have any limits on integers.) For those who wanted to handle large numbers in C/C++, lets discuss an approach for how to multiply large numbers.

We use arrays to store the numbers.
Why? Because we do not have any data type which could store big integers say around 10^3 digits.
How? Each digit of integer is stored in each index in the array. Lets store them in reverse order for simpler calculations.

Now we have two integers(A,B) in array each of length L1,L2 respectively. Product of these two numbers will be at most L1+L2. So lets take an empty Ans[] array of size 2*N.

Procedure :

Step 1 : Multiply index i of B with all the indexes j of A. Add the product to value in Ans[k] where 0 <= i < L2, 0 <= j < L1, k = i+j.
Step 2 : Repeat step 1 till i = L2. (Picture how you multiply two large numbers on a paper).
Step 3 :
for each i in range(0,L1+L2)
TMP = X/10. X = X%10. Y = Y+TMP.
X = A[i]
Y = A[i+1]
TMP = temporary variable.
Step 4 : reverse the array Ans, and that will be the final product.

Code:

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

int main()
{
    int a[100],b[100];
    int ans[200]={0};
    int i,j,tmp;
    char s1[101],s2[101];
    scanf(" %s",s1);
    scanf(" %s",s2);
    int l1 = strlen(s1);
    int l2 = strlen(s2);
    for(i = l1-1,j=0;i>=0;i--,j++)
    {
        a[j] = s1[i]-'0';
    }
    for(i = l2-1,j=0;i>=0;i--,j++)
    {
        b[j] = s2[i]-'0';
    }
    for(i = 0;i < l2;i++)
    {
        for(j = 0;j < l1;j++)
        {
            ans[i+j] += b[i]*a[j];
        }
    }
    for(i = 0;i < l1+l2;i++)
    {
        tmp = ans[i]/10;
        ans[i] = ans[i]%10;
        ans[i+1] = ans[i+1] + tmp;
    }
    for(i = l1+l2; i>= 0;i--)
    {
        if(ans[i] > 0)
            break;
    }
    printf("Product : ");
    for(;i >= 0;i--)
    {
        printf("%d",ans[i]);
    }
    return 0;
}

Input :
150353265326
22055653351

Output:
Product : 3316139500221184007426

Related problems : Small Factorials(FCTRL2)
My Solution for Small Factorials

Advertisements

Maximum number of 1’s in a submatrix of given area in a binary matrix

Firstly, let me make the statement clear. You will be given a binary matrix. A binary matrix is one which only consists of 1’s and 0’s. You will be asked to find a maximum number of 1’s in rectangular sub-matrix of a given area.

Naive Approach:
Find all possible rectangles for given area.
For all possible rectangles in given matrix, find number of 1’s in given area.

(I will be discussing for a square matrix of dimensions NxN. Similar solution for any rectangular matrix can be constructed)

for(i = 1;i <= N;i++)
{
	if(area%i == 0 && area/i <= N) 
	{//(area/i) should be less than N else the rectangle goes is out of NxN
		x = i;
		y = area/i;
		for(j = 1;j <= N;j++)
		{
			for(k = 1;k <= N;k++)
			{
				if(j+x-1 <= N && k+y-1 <= N)
				{//checking if other ends lie in range of matrix dimensions
					temp = 0;
					for(l = j; l <= j+x-1 ; l++)
					{//here I find number of 1's in the rectangle
						for(m = k;m <= k+y-1; m++)
						{
							if(a[l][m] == 1)
								temp++;
						}
					}
					if(temp > max)
						max = temp;
				}
				if(j+y-1 <= N && k+x-1 <= N)
				{//this is another rectangle of same dimensions but different orientation
					temp = 0;
					for(l = j; l <= j+y-1 ; l++)
					{
						for(m = k;m <= k+x-1; m++)
						{
							if(a[l][m] == 1)
								temp++;
						}
					}
					if(temp > max)
						max = temp;
				}
			}
		}
	}
}
printf("%d\n",max);

This approach takes a long time to give output for even a values of N around 100. Let us now learn a better approach to this problem.

Solving using Dynamic programming :
We can construct a 2d DP where dp[x][y] has number of 1’s in submatrix a[i][j] where 1 ≤ i ≤ x and 1 ≤ j ≤ y.
The DP can be constructed by this formula

dp[i][j] = 	dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]	    ,if a[i][j] = 0
		dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + 1  ,if a[i][j] = 1

In single statement,

dp[i][j] =     dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + a[i][j]

Understanding the formula : For dp[x][y], we add (number of 1’s in sub-matrix a[i][j], where 1 ≤ i ≤ x and 1 ≤ j ≤ y-1) and (number of 1’s in sub-matrix a[i][j], where 1 ≤ i ≤ x-1 and 1 ≤ j ≤ y).
In doing this we add a sub-matrix a[i][j], where 1 ≤ i ≤ x-1 and 1 ≤ j ≤ y-1 twice. So we subtract that value from the sum.
And lastly, we check if the value at a[i][j] is 1 or not and add the value to sum.

Now we find all possible dimensions of the rectangles, and find number of 1’s in all these rectangles. Return maximum of values found as answer.

How to find number of 1’s in a rectangle now? For example, you are at index (x,y) and dimensions of rectangle is (r,s), number of 1’s in that rectangle would be,

dp[x+r-1][y+s-1] - (dp[x+r-1][y-1] + dp[x-1][y+s-1]) + dp[x-1][y-1].

This is much similar as the way in DP formula that we discussed earlier.

void constructDP(int a[][1001],int dp[][1001])
{
	for (int i = 0; i <= n; ++i)
	{
		dp[0][i] = 0;
		dp[i][0] = 0;
	}
	for (int i = 1; i <= n; ++i)
	{
		for(int j = 1;j <= n; ++j)
		{
			dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + a[i][j];
		}
	}
}

int solve(int a[][1001],int dp[][1001],int n)
{
	constructDP(a,dp);
	ans = INT_MAX;
	for (int i = 1; i <= n; ++i)
	{
		if(count%i == 0 && count/i <= n)
		{
			x = i;
			y = count/i;
			for(int j = 1;j <= n;j++)
			{
				for(int k =1; k <= n;k++)
				{
					if((j+x-1 <= n) && (k+y-1 <= n))
						ans = max(ans, dp[j+x-1][k+y-1]-dp[j-1][k+y-1]-dp[j+x-1][k-1]+dp[j-1][k-1]);
					if((j+y-1 <= n) && (k+x-1 <= n))
						ans = max(ans, dp[j+y-1][k+x-1]-dp[j-1][k+x-1]-dp[j+y-1][k-1]+dp[j-1][k-1]);
				}
			}
		}
	}
	return ans;
}

Using the function, you can note that, with a O(N2) pre-computation, we reduce a query of finding number of 1’s in a rectangle every time from O(N2) to O(1).

Problems related with this concept : SWAPMATR