Return the result of sum of character arrays

Question

Recently in an interview i was asked a question to write a function which takes two character arrays(integers) as input and returns the output character array.

Function Signature:

char* find_sum(char* a, char* b)

How would one approach this?

Example scenario:

find_sum("12345","32142") = "44487"

Note:

The number of digits can be many(1-100).

Answer 1

Just remember how you did addition in the second grade on the paper.

Answer 2

The answer is probably that you have to ask what is returned? Is this a memory allocated string that should be freed by the user or is this a static memory location that is overwritten the next time the function is called?

char* find_sum(char* a, char* b) {
    static char buf[MAX_STRING];
    ...
    return buf;
}

or

char* find_sum(char* a, char* b) {
    char *buf = malloc(MAX_STRING*sizeof(char));
    ...
    return buf;
}

Giving this answer shows the interviewer that you know more about C than just making an algorithm. (As a side-node: It also shows why a language like java shines in these situations as the garbage collections takes care of freeing the buffer).

Answer 3

itoa(atoi(a) + atoi(b), t, 10); if you want to be lazy, where t is a char[MAX_NUMBER_OF_DIGITS].

The real question regards the output array, as mentioned by other users.

Answer 4

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

char *sum(char *a,char *b);

int main()
{
        char a[] = "100";
        char b[] = "300";
        char *c;
        c = sum(a,b);
        printf("%s",c);
}

char *sum(char *a,char *b)
{
        int x,y,z,z2,zLen;
        char *result;
        x = atoi(a);
        y = atoi(b);
        z = x + y;
        z2 = z;
        /* Determine the length of the string now! */
        for(zLen = 1; z > 0 || z < 0; zLen++)
                z/=10;
        result = (char *)malloc(zLen*sizeof(char)+1);
        sprintf(result,"%d\0",z2);
        return result;
}

Quick and dirty implimentation. Note that I'm not freeing the memory, which is not "ideal". Will fetch you extra brownie points for mentioning that there are no error checks happening here, and no freeing of memory, which is far from ideal in practical situations.

Online Version of Code

Answer 5

You did not mention anything about not using any external command.

We can do this easily on machines that have the bc command. You can add any number of digits:

$ echo "99999999999999999999999999999999+1" | bc
100000000000000000000000000000000
$ 

We call this bc from the C program. We need to construct the right command line as

echo "n1+n2" | bc

and then use popen to read its result. Below is the function to do that. The code lacks many error checking.

char* find_sum(char* a, char* b) {

        int l1 = strlen(a),l2 = strlen(b);
        int cmdLen = l1 + l2 + 30; // 30 to accomodate echo,bc and stuff.

        char *cmd = malloc(cmdLen);    
        snprintf(cmd,cmdLen,"echo \"%s+%s\"|bc",a,b);

        FILE *fp = popen(cmd, "r");

        int max = (l1 > l2) ? l1:l2;
        max += 2; // one for additional digit, one for null.
        char *result = malloc(max);

        fgets(result, max, fp);
        return result;
}

Working link

Answer 6

u can add huge numbers using the char array approach. however you need to delete the char* after using it every time or use some smart pointer.

 char* find_sum(char* a, char* b) {
    int lenA = strlen(a), lenB = strlen(b);
    int max = lenA > lenB ? lenA : lenB; // Get the max for allocation
    char* res = (char*)malloc (max+2);
    memset(res, '0', max +1);      // set the result to all zeros
    res[max+1] = '\0';
    int i=lenA - 1, j = lenB - 1, k = max;
    for (; i >= 0 || j >=0; --i, --j, --k) {
            int sum = 0;
            if (i >= 0 && j>=0)
                    sum = a[i] - '0' + b[j] - '0' + res[k] - '0' ;  // add using carry
            else if (j >= 0)
                    sum =  b[j] - '0' + res[k] - '0' ;     // add the carry with remaining
            else if (i >= 0)
                    sum =  a[i] - '0' + res[k] - '0' ;
            res[k] = sum % 10 + '0';
            res[k-1] = sum / 10 + '0';
    }
    return res;
 }

 int main() {
    printf (" sum = %s ", find_sum("12345432409240242342342342234234234", "9934563424242424242423442424234"));
    return 0;
 }

Note: The precondition for the function is the input char arrays should contain only numbers.

Answer 7

The most obvious answer is internally to use something like atoi and sprintf to convert the numbers to integers, do the sum and return the response as a char* However the important thing here is not what the interviewer is asking but why.

In my experience, the interviewer is probably not wanting you to write a hum-dinger of a solution that covers all angles. What they most likely want to get to is what the most common approach would be, and what are the likely limitations of such a function. I.e.:

1. What happens if your input numbers aren't integers? (e.g. 13.245, 2.3E+7)

2. What happens if your 'numbers' aren't numbers at all?

3. What happens if your input integers are really big? (i.e. ~2^31)

4. How could you detect an error and how would you report it.

5. How would you allocate memory for the resultant string?

6. What would the memory allocation imply for the calling code?

7. What is the efficiency of the function and how could you make it more efficient?

In this way, the interviewer wants to probe your experience of critiquing approaches to problem solving. Naturally, there are many ways of solving this problem. Some of the approaches have side-effects but in certain contexts, these side effects (i.e. integer overflow) may not be greatly important.

Coding is often a trade off between a comprehensive solution and what can be produced quickly (and therefore less expensively) These questions allow the interviewer to get a feel for your understanding of quality - that is, can you design something that is fit for purpose, robust and yet does not take too long to put together - and also your experience of having to identify / resolve common bugs.

Answer 8

Several of the answers mention the use of atoi & itoa functions.

atoi returns int. Your numbers may not fit into an integer data type.

You may try to alleviate the problem (not completely though) using atol, which return a long int, or atoll, which returns a long long int.

Also, itoa is not a standard library function, and hence may not be available on all systems.

Answer 9

Here's another approach. Nothe that I don't like the prototype for find_sum. I'd very much prefer it to be

char *find_sum(char *dst, size_t len, const char *a, const char *b);

letting the caller be responsible for managing resources.

a and b are strings composed of 1 or more digits (and digits only); the result should be freed by caller. Calling find_sum with invalid inputs causes UB :-)

char *find_sum(char *a, char *b) {
  char *res;
  int alen, blen, rlen;
  int carry;

  alen = strlen(a);
  blen = strlen(b);
  rlen = 1 + ((alen > blen) ? alen : blen);
  res = malloc(1 + rlen);
  if (res) {
    int oldlen = rlen;
    res[rlen] = 0;
    carry = 0;
    while (rlen) {
      int tmp;
      if (alen && blen) tmp = a[--alen] - '0' + b[--blen] - '0';
      else if (alen) tmp = a[--alen] - '0';
      else if (blen) tmp = b[--blen] - '0';
      else tmp = 0;
      tmp += carry;
      res[--rlen] = '0' + tmp % 10;
      carry = tmp / 10;
    }
    if (res[0] == '0') memmove(res, res+1, oldlen);
  }
  return res;
}

There's a working version of the function at ideone ( http://ideone.com/O2jrx ).