Question

(a)Design an algorithm that takes two numeric strings s1 and s2 and return another numeric string that represent their sum without using using SHIFT OR any operator +.

(b) Analyze time and space of part (a)

(c)Implement part (a) in your favorite programming language without using 0+0 operator. You

should read the two numeric strings from a FILE input.in and output their addition to standard output.

You Solution will be test on 10,000 test cases. Each test case will include two randomly selected numbers.

i want it in c program

positive number

Answer 1

ALGORITHM : -

1. We will make sure that str1 is of smaller length than str2 as it will help to code our program.

2. We will reverse both string as addition is done from left most significant bit.

3. We will perform add operation digit by digit considering carry.

4. Atlast we will be left with only bigger string digits so we will simply add them considering carry.

5. The resultant string obtained will be in reverse order so we will reverse it to get final answer.

Below program performs addition of two numbers in string format

#include <stdio.h>
#include <string.h>
void strrrev(char str[])
{
   int i = strlen(str) - 1, j = 0;

char ch;
while (i > j)
{
ch = str[i];
str[i] = str[j];
str[j] = ch;
i--;
j++;
}
}
void findSum(char str1[], char str2[])
{
if (strlen(str1) > strlen(str2))
{
   char tmp[100];
   strcpy(tmp, str1);
       strcpy(str1, str2);
       strcpy(str2, tmp);
}
char str[100];
int n1 = strlen(str1), n2 = strlen(str2);
strrrev(str1);
strrrev(str2);
  
int carry = 0,ctr=0;
for (int i=0; i<n1; i++)
{
int sum = ((str1[i]-'0')+(str2[i]-'0')+carry);
str[ctr++]=sum%10 + '0';
carry = sum/10;
}
  
for (int i=n1; i<n2; i++)
{
int sum = ((str2[i]-'0')+carry);
str[ctr++]=sum%10 + '0';
carry = sum/10;
}
  
if (carry)
str[ctr++]=carry+'0';
strrrev(str);
printf("Total Sum=");
for(int i=0;i<ctr;i++)
   printf("%c",str[i]);
  
}
int main()
{
char str1[100] = "12";
char str2[100] = "198111";
findSum(str1, str2);
return 0;
}

#include <stdio.h>
#include <string.h>
void strrrev(char str[])
{
   int i = strlen(str) - 1, j = 0;

char ch;
while (i > j)
{
ch = str[i];
str[i] = str[j];
str[j] = ch;
i--;
j++;
}
}
void doSum(char str1[], char str2[])
{
if (strlen(str1) > strlen(str2))
{
   char tmp[100];
   strcpy(tmp, str1);
       strcpy(str1, str2);
       strcpy(str2, tmp);
}
char str[100];
int n1 = strlen(str1), n2 = strlen(str2);
strrrev(str1);
strrrev(str2);
  
int carry = 0,ctr=0;
for (int i=0; i<n1; i++)
{
int sum = ((str1[i]-'0')+(str2[i]-'0')+carry);
str[ctr++]=sum%10 + '0';
carry = sum/10;
}
  
for (int i=n1; i<n2; i++)
{
int sum = ((str2[i]-'0')+carry);
str[ctr++]=sum%10 + '0';
carry = sum/10;
}
  
if (carry)
str[ctr++]=carry+'0';
strrrev(str);
printf("Total Sum=");
for(int i=0;i<ctr;i++)
   printf("%c",str[i]);
  
}
int main()
{
char str1[100] = "12";
char str2[100] = "198111";
doSum(str1, str2);
return 0;
}

OUTPUT:-

Total Sum=198123

Time complexity = O(n)

Space Complexity = O(n)