Adding two numbers, each digit as a single element of array

Question

After failing to answer an interview question, I went back home and coded the answer for my own improvement. The questions was: Given two arrays containing a number, but with each element of the array containing a digit of that number, calculate the sum and give it in the same format.There must be no leading zeros in the resulting array.

My main concern is that I am being redundant with my logic, or that my code is not clear.

 int *sumOfTwo(int *a1,int *a2, int lengthOfA1, int lengthOfA2, int *lengthDest) {
 //I assume there is error checking for null pointers, etc.
 int *answer;
 int maxSize, minSize, diff;
 int a1IsLongest = TRUE;
 if(lengthOfA1 > lengthOfA2) {
 maxSize = lengthOfA1;
 minSize = lengthOfA2;
 a1IsLongest = TRUE;
 }
 else {
 maxSize = lengthOfA2;
 minSize = lengthOfA1;
 a1IsLongest = FALSE;
 }
 diff = maxSize - minSize;
 answer = malloc(maxSize * sizeof(int));
 int i, extraTen, result;
 extraTen = 0;
 *lengthDest = maxSize;
 //printf("This is lengthDest: %d\n", *lengthDest);
 for (i = maxSize-1; i >= 0; i--) { 
 //add numbers, check if bigger than 10 
 //check if arrays are of different sizes we want to access
 //the end from each, so need to account for this.
 if(diff == 0) {
 //arrays are equal in size
 result = a1[i] + a2[i] + extraTen;
 extraTen = 0;
 }
 else{
 //arrays are different sizes
 if(! ((i - diff) < 0)) {
 if(a1IsLongest) {
 result = a1[i] + a2[i - diff] + extraTen;
 extraTen = 0;
 }
 else {
 result = a1[i - diff] + a2[i] + extraTen;
 extraTen = 0;
 }
 }
 else {
 if(a1IsLongest) {
 result = a1[i] + extraTen;
 extraTen = 0;
 }
 else {
 result = a2[i] + extraTen;
 extraTen = 0;
 }
 }
 }
 //the new malloc can only happen here
 if (result >= 10) {
 //check if at beginning of array
 if(i == 0) {
 maxSize = maxSize + 1;
 *lengthDest = maxSize;
 //printf("This is lengthDest: %d\n", *lengthDest);
 //overflowing, need to realloc
 int *temp = malloc(maxSize * sizeof (int));
 int j;
 //copy old elements into new array 
 for(j = 0; j < maxSize; j++) {
 //printf("index: %d\n", j);
 if(j == 0) {
 temp[j] = 1;
 }
 else if(j == 1) {
 temp[j] = result % 10;
 }
 else {
 temp[j] = answer[j-1];
 }
 }
 free(answer);
 answer = temp;
 return answer;
 }
 else{
 //printf("in the else of the i equals 0.\n");
 answer[i] = result % 10;
 extraTen = 1;
 }
 }
 else {
 //printf(" results is less than 10\n");
 answer[i] = result;
 }
 }
 return answer;
}

Answer 1

 int *sumOfTwo(int *a1,int *a2, int lengthOfA1, int lengthOfA2, int *lengthDest) {
 //I assume there is error checking for null pointers, etc.
 int *answer;
 int maxSize, minSize, diff;
 int a1IsLongest = TRUE;
 if(lengthOfA1 > lengthOfA2) {
 maxSize = lengthOfA1;
 minSize = lengthOfA2;
 a1IsLongest = TRUE;
 }
 else {
 maxSize = lengthOfA2;
 minSize = lengthOfA1;
 a1IsLongest = FALSE;
 }
 diff = maxSize - minSize;
 answer = malloc(maxSize * sizeof(int));

This seems more complicated than necessary. Consider

typedef struct Number {
 int *digits;
 int length;
} Number;
Number *sumOfTwo(const Number *a1, const Number *a2) {
 //I assume there is error checking for null pointers, etc.
 if (a1->length > a2->length) {
 return _sumOfTwo(a1, a2);
 } else {
 return _sumOfTwo(a2, a1);
 }
}
Number *_sumOfTwo(const Number *a1, const Number *a2) {
 Number *answer;
 answer = malloc(sizeof(*answer));
 answer->length = (a1->length + 1);
 answer->digits = calloc(answer->length, sizeof(*(answer->digits)));

Now, a1 is always as long as or longer than a2. So you can do away with your temporary variables. So far, it's about the same length, but we've simplified the function signature.

 if (answer == NULL) {
 // do something
 }
 if (answer->digits == NULL) {
 // do something
 }

As noted elsewhere, you should check that malloc and calloc succeed.

 int i, extraTen, result;
 extraTen = 0;
 *lengthDest = maxSize;
 //printf("This is lengthDest: %d\n", *lengthDest);
 for (i = maxSize-1; i >= 0; i--) { 
 //add numbers, check if bigger than 10 
 //check if arrays are of different sizes we want to access
 //the end from each, so need to account for this.
 if(diff == 0) {
 //arrays are equal in size
 result = a1[i] + a2[i] + extraTen;
 extraTen = 0;
 }
 else{
 //arrays are different sizes
 if(! ((i - diff) < 0)) {
 if(a1IsLongest) {
 result = a1[i] + a2[i - diff] + extraTen;
 extraTen = 0;
 }
 else {
 result = a1[i - diff] + a2[i] + extraTen;
 extraTen = 0;
 }
 }
 else {
 if(a1IsLongest) {
 result = a1[i] + extraTen;
 extraTen = 0;
 }
 else {
 result = a2[i] + extraTen;
 extraTen = 0;
 }
 }
 }

Now this code we can make a lot shorter with fewer checks.

 int i = 0;
 for (; i < a2->length; i++) {
 answer->digits[i] += a1->digits[i] + a2->digits[i];
 process_carry(answer->digits, i);
 }
 for (; i < a1->length; i++) {
 answer->digits[i] += a1->digits[i];
 process_carry(answer->digits, i);
 }

Since a1 is always longer than a2, we don't have to check the lengths.

We avoid checking the diff by changing the order from most significant digit at the zero position to the least significant at the zero position. Now we have to use two loops, but we don't have to check anything.

We can use += because calloc zeroes out its elements. If there's a carry, we add to it. If not, there's already a 0 there.

Create process_carry:

 const int BASE = 10;
 void process_carry(int *digits, int position) {
 if (digits[position] > BASE) {
 digits[position] -= BASE;
 digits[position+1] += 1;
 }
 }

You can create a more generic version by replacing the if with a while. Or

 void process_carry(int *digits, int position) {
 digits[position+1] += digits[position] / BASE;
 digits[position] %= BASE;
 }

This may be more efficient than using a while.

Note how neither version requires an extraTen variable.

This also uses BASE rather than the magic number 10. Now if you want to change to a different base, you can do so easily.

 //the new malloc can only happen here
 if (result >= 10) {
 //check if at beginning of array
 if(i == 0) {
 maxSize = maxSize + 1;
 *lengthDest = maxSize;
 //printf("This is lengthDest: %d\n", *lengthDest);
 //overflowing, need to realloc
 int *temp = malloc(maxSize * sizeof (int));
 int j;
 //copy old elements into new array 
 for(j = 0; j < maxSize; j++) {
 //printf("index: %d\n", j);
 if(j == 0) {
 temp[j] = 1;
 }
 else if(j == 1) {
 temp[j] = result % 10;
 }
 else {
 temp[j] = answer[j-1];
 }
 }
 free(answer);
 answer = temp;
 return answer;
 }
 else{
 //printf("in the else of the i equals 0.\n");
 answer[i] = result % 10;
 extraTen = 1;
 }
 }
 else {
 //printf(" results is less than 10\n");
 answer[i] = result;
 }
 }
 return answer;

This could be a lot simpler.

 if (answer->length > 1 && answer->digits[answer->length - 1] == 0) {
 answer->length--;
 realloc(answer->length * sizeof(answer->digits[0]));
 if (answer->digits == NULL) {
 free(answer->digits);
 // fail gracefully
 }
 }
 return answer;

Now we don't have to copy. And we already handled the carry. We just resize the array if we made it too big to start. And then return the result.

Note that this allows for the situation where we are returning zero while stripping off a single leading zero otherwise.

• FSB: Is Array a typedef for normal array? I have a lot to learn from your answer and Edward's but since I can only accept one I choose yours.
• mdfst13: Oops. I changed names from Array to Number but missed a spot. Edited.

Answer 2

I see some things that may help you improve your code.

Use const where practical

The sumOfTwo() function doesn't (and probably shouldn't) modify the passed integer arrays, so they should be declared const.

Show all required headers

The code uses malloc and free but the code does not show a the required include file. For code reviews (and job interviews!), it's best to list the required includes. This code needs only:

#include <stdlib.h>

Use stdbool.h when needed

This code contains lines like this:

int a1IsLongest = TRUE;

However, there are already bool types and values supported in the stdbool.h header. Prefer those to non-standard types and values. The line above would then be:

bool a1IsLongest = true;

Fix formatting

The indentation is not consistent, and in one case, there's a space between else and the following { but in other case there's no space. Which convention you use is less important than choosing one and following it consistently.

Simplify your code

There are a number of extra variables and comparisons to determine which array is larger. Why not instead simply assume that a1 is longer than or equal in length to a2 and then make that true? It would simplify the code a lot. For example, one could start the code this way:

if (lengthOfA1 < lengthOfA2) {
 // swap the arguments to ensure a1 is not shorter than a2
 int *temp = a1;
 int templen = lengthOfA1;
 a1 = a2;
 lengthOfA1 = lengthOfA2;
 a2 = temp;
 lengthOfA2 = templen;
}

Assume a convenient data structure unless otherwise specified

It's not clear whether you were told that the data structure had the least significant or most significant digit first or whether either had leading zeroes. The most convenient data structure would actually be to store the data with the least significant digit first, as I'll demonstrate in the next suggestion.

Allocate memory only once

The current code allocates some memory and then may allocate again if more is needed, copying the elements from the old to the new array. There are several strategies that would allow you to allocate memory only once.

The first is to note that the maximum additional memory required would be exactly one int and to simply allocate enough space for that, with the understanding that there would be, potentially, a leading zero in the answer.

The second would be to determine if a carry will be required and allocate space accordingly. One way to do that would be to make two passes through the data.

The other possibility is to adjust the allocated length after calculation. This could be done very simply using the realloc function.

Prefer "less expensive" to "more expensive" operations

If the digits are decimal digits (not stated, but assumed), then the largest possible sum will be 9+9=18, so the largest possible carry value is 1. If the resulting value is greater than 10, the current code uses this code:

answer[i] = result % 10;

The % operator typically does a division which is computationally expensive on many platforms. Better is to simply use subtraction and the fact that the carry can only possibly be equal to 1 or 0.

if (result >= 10) {
 result -= 10;
 carry = 1;
}

Check for memory allocation failure

Calls to malloc can fail. Robust code should check for that and handle the out-of-memory condition appropriately.

Putting it all together

Here's a version incorporating all of these suggestions:

int *sumOfTwo(const int *a1, const int *a2, int lengthOfA1, int lengthOfA2, int *lengthDest)
{
 if (lengthOfA1 < lengthOfA2) {
 // swap the arguments to ensure a1 is not shorter than a2
 const int *temp = a1;
 int templen = lengthOfA1;
 a1 = a2;
 lengthOfA1 = lengthOfA2;
 a2 = temp;
 lengthOfA2 = templen;
 }
 *lengthDest = lengthOfA1 + 1;
 int *result = malloc(*lengthDest*sizeof(a1[0]));
 if (result == NULL) {
 *lengthDest = 0;
 return NULL;
 }
 // copy a1 into result 
 memcpy(result, a1, lengthOfA1*sizeof(a1[0]));
 result[lengthOfA1] = 0;
 int carry = 0;
 int *end = result + *lengthDest;
 int val;
 // add in place
 for (int *digit = result; digit != end; ++digit) {
 val = carry + *digit;
 if (lengthOfA2) {
 val += *a2++;
 --lengthOfA2;
 }
 if (val >= 10) {
 val -= 10;
 carry = 1;
 } else {
 carry = 0;
 }
 *digit = val;
 }
 return result;
}

Test harness

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
// sumOfTwo() goes here
void printnum(const int *num, int len, int desiredlen)
{
 for (; desiredlen > len; --desiredlen) {
 printf(" ");
 }
 for (num += len - 1; len; --len, --num) {
 printf("%u", *num);
 }
 puts("");
}
struct number {
 int len;
 int digits[5];
};
struct test {
 struct number n1, n2, expected;
};
struct test tests[] = {
 { { 1, {9} }, { 1, {9} }, { 2, { 8, 1 } }}, 
 { { 3, {8, 9, 9}}, {2, {1, 9}}, { 4, { 9, 8, 0, 1}}},
 { { 3, {8, 9, 9}}, {3, {0, 0, 1}}, { 4, {8, 9, 0, 1}}},
};
bool doTest(const struct test* t) {
 int lengthDest;
 int *answer = sumOfTwo(t->n1.digits, t->n2.digits, t->n1.len, t->n2.len, &lengthDest);
 printnum(t->n1.digits, t->n1.len, 5);
 printnum(t->n2.digits, t->n2.len, 5);
 puts("-----");
 printnum(answer, lengthDest, 5);
 if (lengthDest != t->expected.len) {
 free(answer);
 return false;
 }
 for (int i = 0; i < lengthDest; ++i) {
 if (t->expected.digits[i] != answer[i]) {
 free(answer);
 return false;
 }
 }
 free(answer);
 return true;
}
int main()
{
 int testcount = sizeof(tests) / sizeof(tests[0]);
 for (int i=0; i < testcount; ++i) {
 printf("Test %d: %s\n\n", i+1, doTest(&tests[i]) ? "OK " : "BAD");
 }
}

Test result

Here is the output of the test program:

 9
 9
-----
 18
Test 1: OK 
 998
 91
-----
 1089
Test 2: OK 
 998
 100
-----
 1098
Test 3: OK 

• Caridorc: Are you sure that a conditional jump (if) is faster than division remainder (%)? I think it needs benchmarking before it can be said for sure.
• Edward: Any proposed efficiency optimization should be tested on the actual target machine, and ideally with some representative data.
• FSB: You're answer is giving me a random result. I am declaring int a1[] = {9}; int a2[] = {9}; int destArraySize = NULL and calling the function as sumOfTwo(a1,a2, <length of a1>, <length of a2>, &destArraySize); (with the elements in <> calculated correctly.
• FSB: One of the requirements was that there would be no leading zeros in the answer. Thank you for pointing that out, I've updated my question.
• Edward: You're right. There was an error in my memory allocation, but I've fixed that now and also added test data and routine to my answer.

Answer 3

Ternary simplification + common code extraction

(After fixing the indentation) I start with:

 if(a1IsLongest) {
 result = a1[i] + extraTen;
 extraTen = 0;
 }
 else {
 result = a2[i] + extraTen;
 extraTen = 0;
 }

I extract extraTen = 0 out:

 if(a1IsLongest) {
 result = a1[i] + extraTen;
 }
 else {
 result = a2[i] + extraTen;
 }
 extraTen = 0;

I use a ternary conditional expression because only the value changes, the action remains assigning result in both cases:

 result = (a1IsLongest ? a1 : a2)[i] + extraTen;
 extraTen = 0;

This small chunk of code is now simpler and more self-evident.

Answer 4

Testing for i == 0 at each iteration of the loop seems wasteful. Another way to detect overflow is to test for extraTen after the loop:

 for (i = maxSize-1; i >= 0; i--) {
 do_calculations;
 }
 if (extraTen) {
 answer = reallocate_and_copy(answer, maxSize);
 answer[0] = 1;
 }

Similarly, there is no need to test which array is longer at each iteration. Do it once at the very beginning:

 if (lengthOfA1 < lengthOfA2) {
 int * tmp = a1;
 a1 = a2;
 a2 = tmp;
 int tmp1 = lengthOfA1;
 lengthOfA1 = lengthOfA2;
 lengthOfA2 = tmp;
 }

Now you are guaranteed that a1 is longer than a2.

Finally I recommend to split the loop in two:

 for (j = lengthOfA1 - 1, i = lengthOfA2 - 1; i >= 0; --i, --j) {
 add_array_elements;
 }
 for (; j >= 0; --j) {
 propagate_carry;
 }

Answer 5

Note: I approached this answer with the reasoning that the right-most element of our data structure would contain the LSD, since this is more logical in the real world way of thinking about numbers.

In my mind, int is illogical to the entirety of this question. Let me explain.

If we break a number into its places, 5662 becoming { 5, 6, 6, 2 }, it would be impossible for any one place to contain a negative number. There should be no need for signs here, and no need to give the impression that we might account for signed numbers. We won't - not in this answer! (If we need to consider a signed signifier, we could add a third member to our struct.)

For that reason, our starting type is:

typedef struct {
 unsigned *digits;
 size_t length;
} number;

But before that, headers!

#include <stdlib.h>
#include <string.h>

We're going to be doing some memory oriented operations (malloc, free, memcpy), so we'll need these two. No need for <stdbool.h>, as you'll see in a little, we'll be (ab)using simple unsigned flags.

Next, our function signatures.

static void swap_numbers (const number **one, const number **two)
number *add_numbers (const number *longer, const number *shorter)

Pretty standard. We'll hide some pointer swapping away in a helper function.

All that's left is to go through the code. Throughout this implementation, we rely on our understanding of when certain expressions evaluate to 0 or 1, and how other expressions consume these flags. There are times when we omit certain verbosities, and times when we avoid certain optimizations, in favour of keeping it simple.

(It should be stated that I'm not a fan of explicit expressions such as x != NULL, or n != 0, or even n > 0 when using unsigned types since this is really a sneaky n != 0, which is of course n.)

digits.h

The header.

#ifndef DIGIT_ADDITION
#define DIGIT_ADDITION
#include <stdlib.h>
typedef struct {
 unsigned *digits;
 size_t length;
} number;
extern number *add_numbers (const number *longer, const number *shorter);
#endif

digits.c

The bulk of our code.

#include <stdlib.h>
#include <string.h>
#include "digits.h"
static void swap_numbers (const number **one, const number **two) {
 const number *tmp = *one;
 *one = *two;
 *two = tmp;
}
number *add_numbers (const number *longer, const number *shorter) {
 if (!longer || !shorter) return NULL; // User messed up, bail.
 number *result = malloc(sizeof (number));
 if (!result) return NULL; // malloc failed, bail.
 if (shorter->length > longer->length) {
 swap_numbers(&shorter, &longer); // Swap our pointers.
 }
 // Maximum length possible, so let's just account for it,
 // and recover later if needed.
 result->length = longer->length + 1;
 unsigned buffer[result->length]; // Our temporary memory space. Yum.
 size_t ldex = longer->length; // longer index
 size_t sdex = shorter->length; // shorter index
 const unsigned base = 10;
 // Our most recent carry, either `0` or `1`.
 // We haven't done any math yet, so this is initialized as zero.
 unsigned carry = 0;
 while (ldex) {
 // Compute our basic sum. Note the prefix operator(s).
 unsigned sum = carry + longer->digits[--ldex];
 if (sdex) {
 sum += shorter->digits[--sdex];
 // sdex will eventually equal zero, getting our final index,
 // and our shorter number will be finished.
 }
 // Here we rely on (comparison) operators evaluating to `0` or `1`.
 // Two birds, one stone:
 // We get our carry, and use it to determine if our sum needs adjustment.
 if ((carry = sum >= base)) {
 sum -= base;
 }
 // Our buffer is a teensy bit larger than our longer number.
 buffer[ldex + 1] = sum;
 }
 // Again, we rely on (logical) operators evaluating to `0` or `1`.
 // This comes in handy in a little bit.
 unsigned leading_zero = !carry;
 if (leading_zero) {
 result->length--; // Chomp our leading zero.
 } else {
 buffer[0] = carry; // Or set our carry.
 }
 // Compute our final memory requirement.
 size_t final_size = result->length * sizeof (unsigned);
 // Get some memory.
 result->digits = malloc(final_size);
 if (result->digits) {
 // malloc worked. Copy our buffer into our results.
 // `leading_zero` now helps us with a little pointer arithmetic.
 memcpy(result->digits, buffer + leading_zero, final_size);
 } else {
 free(result); // Malloc failed, cleanup.
 result = NULL;
 }
 return result; // Done!
}

prog.c

A little program.

#include <stdlib.h>
#include <stdio.h>
#include "digits.h"
int main (void) {
 number n = {
 .digits = (unsigned [7]) { 6, 5, 7, 6, 4, 2, 3 },
 .length = 7
 };
 // { 9, 6, 0, 2, 0, 4, 8, 7, 3, 5 }
 number m = {
 .digits = (unsigned [10]) { 9, 5, 9, 5, 4, 7, 2, 3, 1, 2 },
 .length = 10
 };
 number *result = add_numbers(&n, &m);
 if (result) {
 for (size_t i = 0; i < result->length; i++) {
 printf("[%u]", result->digits[i]);
 };
 printf("\n");
 free(result->digits);
 free(result);
 }
}

Side note, I applaud your use of a space the second time you use the sizeof operator, but do try to be consistent throughout when it comes to formatting.