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

Inverting sub-array to get maximum 1’s.

Let there be an array containing only two different elements. Lets consider them to be 0 and 1. You have to find total number of 1’s you could make from this array after performing some task. And the task is to select a sub-array and invert each of its element(Convert each of the element from 0 to 1 or 1 to 0 for every element in sub-array).

This problem certainly have a simple approach. Check for all subsets and count number of resulting 1’s in the array. That would result in an O(N3) solution and the pseudocode would look something like this

for i = 0 to n
    for j = i to n
        for k = i to j
            invert(elements)
            count(number of 1s)
            revert(elements)

That is very high complexity and surely is not expected. But the solution for above problem can be condensed to O(n) complexity. Yeah! That’s great!! But how?

First count number of 1’s in given array and store them(C). Now make another array such that for all 0’s in given array, corresponding indexes in new array have value 1 and for all 1’s in given array, corresponding indexes have value of -1. Now find Maximum sub-array sum for this new array. It gives number of 1’s that would be added by the sub-array to actual array after being inverted/flipped. It also removes all previously counted 1’s in that part of sub-array. How? all 0’s are 1’s now which will be added to MaxSubarray sum and all 1’s are -1’s now which will be subtracted from that sum.

Adding C and M would result in number of maximum 1’s that could be formed as per the question.

C = 0
M = 0
for i = 0 to n
    if A[i] = 1
        C = C+1
for i = 0 to n
    if A[i] = 1
        B[i] = -1
    else if B[i] = 0
        B[i] = 1
M = MaxSubarraySum(B)
print C + M
Example :
Array     :  1 0 0  1 0  1  1 0 0 0  1 0 0  1  1  1  1 0 0  1
Inverting : -1 1 1 -1 1 -1 -1 1 1 1 -1 1 1 -1 -1 -1 -1 1 1 -1
Count of 1's = 10
Maximum Subarray sum = 4

Answer for given array = 10 + 4 = 14
Final Array : 1 0 0 1 0 1 1 1 1 1 0 1 1 1 1 1 1 0 0 1

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'