Hi Lippy ,
Here is the code. Its pretty lengthy. Its the code for Bishops problem(spoj.pl/problems/BISHOPS/). I am trying to solve the problem by finding 2*(n-1) which I believe is the solution to this problem but since it involves very large numbers I am forced to use string multiplication.
Please ask me questions if the code is unclear to you. Let me know of the areas within the code that needs revision as they might potentially lead to a SIGSEGV exception.
#include<stdio.h>
#include<string.h>
#include<list>
#include<string>
using namespace std;
//This method decrements the given number represented by string n by 1
string DECR(string n)
{
int len = n.length();
int digit;
int i = len-1;
while(i > 0)
{
digit = n.c_str()[i] - '0';
if( digit > 0)
{
digit --;
n.replace(i,1,1,digit+'0');
return n;
}
else
{
n.replace(i,1,1,'9');
i--;
}
}
if (i == 0 && len > 1)
{
n.erase(0,1);
return n;
}
else
{
digit = n.c_str()[i] - '0';
digit --;
n.replace(i,1,1,digit+'0');
return n;
}
}
// strrev since the ANCI C doesnt come with it
char* strrev(char* input,int len)
{
int i = 0;
int j = len;
char temp;
while(i<j)
{
temp = input[i];
input[i] = input[j];
input[j] = temp;
i++;
j--;
}
return input;
}
// the acutal method that multiplies the 2 long numbers in the form of a string.
string LongMultiplication(string n1,string n2)
{
int l1 = n1.length();
int l2 = n2.length();
// here I make sure that string n1 represents the greater of the 2 numbers.
// this will help in making my calculations and memory allocations.
if ( l2 > l1 )
{
//swap strings
string temp = n1;
n1.assign(n2);
n2.assign(temp);
int templen = l1;
l1 = l2;
l2 = templen;
}
char* result = (char*)malloc(sizeof(char)*(l1+l2+3));
int **arr;
arr = new int*[l1];
int i = 0;
// here a allocate a 2D array to store the rows to be added.
while( i < l1)
{
arr[i] = new int[l2+l1+1];
i++;
}
for(i = 0; i<l1;i++)
{
for(int j = 0;j < l2+l1+1;j++)
{
arr[i][j] = 0;
}
}
i = l2-1;
int j = l1-1;
int posj = l2+l1;
int posi = 0;
int multipilcand_digit;
int resultant;
unsigned long long carry=0;
int iter =0;
int outeriter = 0;
// here I perform the calculations of all the rows(as the way we do it manually with pen and paper) while performing
// multiplication
while( i >= 0 && outeriter < l2)
{
int multiplierdigit = n2.c_str()[i] - '0';
posj = l2+l1-outeriter;
carry = 0;
j = l1 - 1;
iter = 0;
while(j >= 0 && iter < l1)
{
multipilcand_digit = n1.c_str()[j] - '0';
resultant = (multiplierdigit * multipilcand_digit+ carry )%10;
arr[posi][posj] = resultant ;
carry = (multiplierdigit * multipilcand_digit+ carry ) / 10;
posj--;
j--;
iter ++;
}
if(carry > 0)
arr[posi][posj] = carry;
i--;
outeriter++;
posi++;
}
unsigned long long ch;
carry = 0;
int k = 0;
unsigned long int pow = 10;
// Here I add all the rows that were computed during the earlier step
for(int j= l2+l1;j>=0 && k>=0;j-- )
{
ch = 0;
for(int i=0;i<l1;i++)
{
ch += arr[i][j];
}
ch += carry;
carry = ch/10;
ch = ch%10;
while( ch > 10 )
{
pow = pow*(10);
ch=ch%pow;
}
ch = ch+'0';
result[k] = ch;
k++;
}
if(carry)
{
ch = carry+'0';
result[k++] = ch;
}
result[k] = '\0';
result = strrev(result,k-1);
char* backup = result;
while( result[0] == '0')
result++;
// free the 2d array
i = 0;
while( i < l1)
{
delete[] (arr[i]);
i++;
}
delete[] (arr);
string res(result);
free(backup);
return res.c_str();
}
int main()
{
char temp[101];
list<string> List;
int count =0;
while((scanf("%s",&temp) != EOF))
{
string str(temp);
List.push_back(str);
count++;
}
int i = 0;
string str,res;
while(i < count)
{
str = List.front();
if( strcmp(str.c_str(),"1") == 0 )
{
printf("%s\n",1);
continue;
}
str = LongMultiplication((DECR(str.c_str())),"2");
printf("%s\n",str.c_str());
List.pop_front();
i++;
}
return 0;
}
Thank you,
Harish
